농장에는 개의 행과 개의 열이 있다. 서로 다른 개의 칸에 작물이 하나씩 있다. 번 작물은 행 열에 있다.
수확 기계는 한 열에서 연속된 행들을 차지한다. 처음에는 행 열 한 칸을 차지한다. 이 칸에는 작물이 없다.
기계에 다음 두 연산을 할 수 있다.
연산 후 기계가 차지하게 된 칸에 작물이 있으면 그 작물을 즉시 수확한다. 어떤 연산에서도 기계의 일부가 농장 밖으로 나갈 수 없다.
모든 작물을 수확하는 데 필요한 연산 횟수의 최솟값을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 한 줄에 필요한 연산 횟수의 최솟값을 출력한다.
번 케이스에서는 확장 번과 오른쪽 이동 번으로 모든 작물을 수확할 수 있다. 번 케이스에서는 확장 번과 왼쪽 이동 번이 필요하다.
각 케이스는 다음과 같은 형식으로 주어진다.
는 테스트 케이스의 수이다. 각 케이스에서 농장의 크기, 기계의 초기 위치, 작물의 수와 각 작물의 위치가 순서대로 주어진다.
| 2 | 17 | (). |
| 3 | 23 | (). |
| 4 | 47 | 추가적인 제약이 없다. |
