일부 붙잡기

Bundle은 동물 연구원이며 K마리의 개를 관찰하러 가야 한다. 그녀는 0, 1, 2, 3 등과 같이 연속된 숫자가 미터 간격으로 표시된 수평 도로에 산다. 그녀는 위치 0에 있는 자신의 집에서 출발한다. 도로에는 N마리의 개도 있다. i번째 개는 도로에서 그녀의 집으로부터 오른쪽으로 $P_{i}$미터 떨어져 있다(여러 마리의 개가 같은 위치에 있을 수 있다).

개들은 서로 다른 색을 가지며, 색은 양의 정수로 나타낸다. i번째 동물의 색은 $A_{i}$이다.

Bundle은 자신의 집에 있을 때 현재 입고 있는 셔츠의 색을 바꿀 수 있다. 개들은 매우 수줍음이 많으므로 이는 중요하다! Bundle은 개와 같은 위치에 있고 그 개와 같은 색의 셔츠를 입고 있을 때만 그 개를 관찰할 수 있다.

Bundle이 도로에서 왼쪽이나 오른쪽으로 한 미터 이동하는 데에는 일 초가 걸린다. 셔츠를 갈아입거나 개를 관찰하는 데에는 시간이 걸리지 않는다.

Bundle이 K마리의 개를 관찰하는 데 걸리는 최소 시간은 얼마인가? K마리의 개를 관찰한 뒤에는 집으로 돌아올 필요가 없음에 유의하라.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 1 ≤ K ≤ N. 1 ≤ $A_{i}$ ≤ 1000. 1 ≤ $P_{i}$ ≤ $10^{5}$.

테스트 세트 1 (공개)

1 ≤ N ≤ 50.

테스트 세트 2 (비공개)

1 ≤ N ≤ 1000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 N과 K가 포함된 줄로 시작하며, 이들은 각각 수직선 위에 있는 개의 수와 Bundle이 관찰해야 하는 개의 수이다. 두 번째 줄에는 N개의 정수가 주어지며, 그중 i번째 정수 $P_{i}$는 i번째 개의 위치이다. 세 번째 줄에는 N개의 정수가 주어지며, 그중 i번째 정수 $A_{i}$는 i번째 개의 색이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고, y는 Bundle이 K마리의 개를 관찰하는 데 필요한 최소 시간이다.

예제 케이스 #1에는 N = 4마리의 개가 있으며, Bundle은 K = 3마리의 개를 관찰해야 한다. 이를 달성할 수 있는 한 가지 방법은 다음과 같다.

• 색이 3인 셔츠를 입는다.

• 오른쪽으로 한 미터 이동하고 그곳의 개를 관찰한다.

• 다시 오른쪽으로 한 미터 이동하고 그곳의 개를 관찰한다.

• 왼쪽으로 두 미터 이동하여 집으로 돌아온다.

• 색이 2인 셔츠로 갈아입는다.

• 오른쪽으로 네 미터 이동하고 그곳의 개를 관찰한다.

총 소요 시간은 Bundle에게 8초이며, 이는 가능한 최소 시간이므로 답은 8이다.

예제 케이스 #2에는 N = 4마리의 개가 있으며, Bundle은 K = 3마리의 개를 관찰해야 한다. 이를 달성할 수 있는 한 가지 방법은 다음과 같다.

• 색이 1인 셔츠를 입는다.

• 오른쪽으로 한 미터 이동하고 그곳의 개를 관찰한다.

• 왼쪽으로 한 미터 이동하여 집으로 돌아온다.

• 색이 8인 셔츠로 갈아입는다.

• 오른쪽으로 두 미터 이동하고 그곳의 개를 관찰한다.

• 다시 오른쪽으로 두 미터 이동하고 그곳의 개를 관찰한다. Bundle은 위치 3에서 지나치는 개를 관찰할 수 없음에 유의하라. 현재 셔츠의 색이 맞지 않기 때문이다(이전에 올바른 색의 셔츠를 입고 있었더라도 마찬가지이다).

총 소요 시간은 Bundle에게 6초이며, 이는 가능한 최소 시간이므로 답은 6이다.

예제 케이스 #3에서는 다음에 유의하라.

• 여러 마리의 개가 같은 위치에 있을 수 있으며

• 개들이 반드시 위치의 오름차순으로 주어지는 것은 아니다.

이 케이스의 답에 대한 설명은 제공되지 않는다.