개 몇 마리 잡기
면접 대비시간 제한30초메모리 제한1024 MB
N마리의 개가 각각 위치와 색을 가지며, Bundle은 0에서 출발해 셔츠 색이 맞는 개만 관찰할 수 있고 셔츠는 집에서만 바꿀 수 있을 때 K마리를 관찰하는 최소 이동 시간을 구한다.
문제
Bundle은 동물 연구자이고, 개 K마리를 관찰하러 가야 한다. 그녀는 0, 1, 2, 3, ...처럼 1미터 단위로 번호가 붙은 수평한 거리에서 산다. 그녀는 위치 0에 있는 집에서 출발한다. 거리 위에는 개 N마리도 있다. i번째 개는 집에서 오른쪽으로 Pi미터 떨어진 곳에 있다(여러 마리가 같은 위치에 있을 수 있다).
개의 색은 서로 다르며, 양의 정수로 나타낸다. i번째 개의 색은 Ai이다.
Bundle이 집에 있으면, 지금 입고 있는 셔츠의 색을 바꿀 수 있다. 개들은 매우 부끄러워하기 때문에 이 점이 중요하다! Bundle은 개와 같은 위치에 있으면서 개와 같은 색 셔츠를 입고 있을 때만 그 개를 관찰할 수 있다.
Bundle이 거리에서 왼쪽이나 오른쪽으로 1미터 움직이는 데 1초가 걸린다. 셔츠를 갈아입거나 개를 관찰하는 데는 시간이 걸리지 않는다.
Bundle이 K마리의 개를 관찰하는 데 필요한 최소 시간은 얼마인가? K마리를 관찰한 뒤 집으로 돌아올 필요는 없다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 뒤따른다. 각 테스트 케이스의 첫 줄에는 수직선 위의 개 수 N과 Bundle이 관찰해야 하는 개 수 K가 주어진다. 둘째 줄에는 N개의 정수가 주어지며, i번째 정수는 i번째 개의 위치 Pi이다. 셋째 줄에는 N개의 정수가 주어지며, i번째 정수는 i번째 개의 색 Ai이다.
출력
각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Bundle이 K마리의 개를 관찰하는 데 필요한 최소 시간이다.
제한
- 1 ≤ T ≤ 100.
- 1 ≤ K ≤ N.
- 1 ≤ Ai ≤ 1000.
- 1 ≤ Pi ≤ 105.
힌트
예제 1에서 N = 4마리의 개가 있고, Bundle은 K = 3마리의 개를 관찰해야 한다. 한 가지 방법은 다음과 같다:
- 색 3인 셔츠를 입는다.
- 오른쪽으로 1미터 움직여 그곳의 개를 관찰한다.
- 다시 오른쪽으로 1미터 움직여 그곳의 개를 관찰한다.
- 왼쪽으로 2미터 움직여 집으로 돌아온다.
- 색 2인 셔츠로 갈아입는다.
- 오른쪽으로 4미터 움직여 그곳의 개를 관찰한다.
모두 합쳐 Bundle은 8초가 걸리며, 이는 가능한 최소 시간이므로 답은 8이다.
예제 2에서 N = 4마리의 개가 있고, Bundle은 K = 3마리의 개를 관찰해야 한다. 한 가지 방법은 다음과 같다:
- 색 1인 셔츠를 입는다.
- 오른쪽으로 1미터 움직여 그곳의 개를 관찰한다.
- 왼쪽으로 1미터 움직여 집으로 돌아온다.
- 색 8인 셔츠로 갈아입는다.
- 오른쪽으로 2미터 움직여 그곳의 개를 관찰한다.
- 다시 오른쪽으로 2미터 움직여 그곳의 개를 관찰한다. Bundle이 위치 3에서 지나친 개는 관찰할 수 없다는 점에 유의하라. 셔츠의 색이 맞지 않기 때문이다(이전에는 맞는 색 셔츠를 입고 있었지만).
모두 합쳐 Bundle은 6초가 걸리며, 이는 가능한 최소 시간이므로 답은 6이다.
예제 3에서 유의할 점:
- 여러 마리의 개가 같은 위치에 있을 수 있고
- 개들이 위치 순서대로 주어진다는 보장이 없다.
이 케이스의 답에 대한 설명은 제공되지 않는다.