음식 매점

모두가 길거리 음식을 좋아하며, 특히 Bitetown의 지역 주민들은 더욱 그렇다! 이런 이유로, 당신은 Bitetown의 중심가에 정확히 K개의 음식 매점과 하나의 창고를 짓기로 했다.

중심가는 길이가 $10^{9}$미터인 긴 수평선이다. 매점이나 창고를 지을 수 있는 지점이 N개 있다. 거리의 다른 곳에는 지을 수 없다. i번째 지점은 거리의 왼쪽 끝에서 $X_{i}$미터 떨어져 있다.

i번째 지점에는 매점 또는 창고 중 최대 하나만 지을 수 있으며(둘 다 지을 수는 없다), 비용은 $C_{i}$달러이다. 또한 창고가 j번째 지점에 있다면, i번째 지점에 매점을 짓는 데에는 |$X_{j}$ - $X_{i}$|달러의 추가 비용이 든다.

정확히 K개의 음식 매점과 하나의 창고를 짓는 최소 비용을 구하라.

제한

테스트 세트당 시간 제한: 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ K < N 모든 i에 대해, 1 ≤ $C_{i}$ ≤ $10^{9}$. 모든 i에 대해, 1 ≤ $X_{i}$ ≤ $10^{9}$. 모든 i ≠ j에 대해, $X_{i}$ ≠ $X_{j}$.

테스트 세트 1 (공개)

2 ≤ N ≤ 100

테스트 세트 2 (비공개)

500 < N ≤ $10^{5}$인 케이스는 최대 5개이다. 나머지 케이스에서는 2 ≤ N ≤ 500이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 K와 N이 포함된 줄로 시작하며, 각각 지어야 하는 매점의 수와 거리에서 건설할 수 있는 지점의 수를 나타낸다.

둘째 줄에는 N개의 정수 $X_{i}$가 주어진다. 이들 중 i번째 정수는 거리의 왼쪽 끝에서 i번째 지점까지의 거리이며, 단위는 미터이다.

셋째 줄에는 N개의 정수 $C_{i}$가 주어진다. 이들 중 i번째 정수는 i번째 지점에 매점 또는 창고를 짓는 비용이다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 K개의 매점을 짓는 최소 비용이다.

예제 케이스 1에서는 K = 2개의 매점과 하나의 창고를 지어야 하며, 건설할 수 있는 지점이 N = 4개 있다. 가능한 해법 중 하나는 3rd 지점에 80달러의 비용으로 창고를 짓고, 2nd 지점과 4th 지점에 두 매점을 짓는 것이다.

• 2nd 지점의 매점 비용은 70 + |3 - 2| = 71달러이다.

• 4번째 지점의 매점 비용은 20 + |3 - 10| = 27달러이다.

총비용은 178달러이고, 이는 가능한 최소 비용이므로 답은 178이다.

예제 케이스 2에서는 K = 1개의 매점과 하나의 창고를 지어야 하며, 건설할 수 있는 지점이 N = 5개 있다. 가능한 해법 중 하나는 2nd 지점에 35달러의 비용으로 창고를 짓고, 3rd 지점에 매점을 짓는 것이다. 이 매점의 비용은 26 + |301-300| = 27달러이다. 총비용은 62달러이고, 이는 가능한 최소 비용이다.

예제 케이스 3에서는 K = 6개의 매점과 하나의 창고를 지어야 하며, 건설할 수 있는 지점이 N = 7개 있다. 가능한 해법 중 하나는 4th 지점에 창고를 짓고 6개의 나머지 지점에 6개의 매점을 짓는 것이다. 총비용이 82달러이고 가능한 최소 비용임을 확인하는 것은 참가자의 연습 문제로 남긴다. 이 예제에서 지점들은 거리의 왼쪽 끝으로부터의 거리를 기준으로 오름차순으로 주어지지 않았다는 점에 유의하라.