음식 노점

Bitetown 주민들은 길거리 음식을 무척 좋아합니다. 그래서 Bitetown의 중심 도로에 정확히 $K$개의 음식 노점과 창고 하나를 짓기로 했습니다.

중심 도로는 길이가 $10^9$미터인 일직선 도로입니다. 노점이나 창고를 지을 수 있는 자리는 $N$곳이며, 그 밖의 곳에는 지을 수 없습니다. $i$번째 자리는 도로 왼쪽 끝에서 $X_i$미터 떨어져 있습니다.

한 자리에는 노점이나 창고 중 하나만 지을 수 있습니다. $i$번째 자리에 노점이나 창고를 지으면 $C_i$달러가 듭니다. 또한 창고가 $j$번째 자리에 있으면, $i$번째 자리에 노점을 짓는 데 $|X_j - X_i|$달러가 추가로 듭니다.

정확히 $K$개의 노점과 창고 하나를 짓는 데 드는 최소 비용을 구하세요.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다. 각 테스트 케이스는 노점의 수 $K$와 자리의 수 $N$이 주어지는 줄로 시작합니다.

둘째 줄에는 $N$개의 정수 $X_1, X_2, ..., X_N$이 주어집니다. $X_i$는 $i$번째 자리가 도로 왼쪽 끝에서 떨어진 거리(미터)입니다.

셋째 줄에는 $N$개의 정수 $C_1, C_2, ..., C_N$이 주어집니다. $C_i$는 $i$번째 자리에 노점이나 창고를 짓는 비용입니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 노점 $K$개를 짓는 최소 비용입니다.

• 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에서는 노점 $K = 2$개와 창고 하나를 지어야 하며, 자리는 $N = 4$곳입니다. 최적 방법 중 하나는 3번째 자리에 80달러짜리 창고를 짓고, 2번째와 4번째 자리에 노점을 짓는 것입니다.

• 2번째 자리의 노점 비용은 $70 + |3 - 2| = 71$달러입니다.
• 4번째 자리의 노점 비용은 $20 + |3 - 10| = 27$달러입니다.

합계는 178달러이며 이것이 최소이므로 답은 178입니다.

예제 2에서는 노점 $K = 1$개와 창고 하나를 지어야 하며, 자리는 $N = 5$곳입니다. 최적 방법 중 하나는 2번째 자리에 35달러짜리 창고를 짓고, 3번째 자리에 노점을 짓는 것입니다. 이 노점의 비용은 $26 + |301 - 300| = 27$달러입니다. 합계는 62달러로 최소입니다.

예제 3에서는 노점 $K = 6$개와 창고 하나를 지어야 하며, 자리는 $N = 7$곳입니다. 최적 방법은 4번째 자리에 창고를 짓고, 나머지 6곳에 노점을 모두 짓는 것입니다. 합계는 82달러이며, 이보다 싼 방법이 없음은 독자가 직접 확인해 보시기 바랍니다. 이 경우 자리들이 거리 순서대로 나열되어 있지 않다는 점에 유의하세요.