Statement
题面语言
농장에는 개의 행과 개의 열이 있다. 서로 다른 개의 칸에 작물이 하나씩 있다. 번 작물은 행 열에 있다.
수확 기계는 한 열에서 연속된 행들을 차지한다. 처음에는 행 열 한 칸을 차지한다. 이 칸에는 작물이 없다.
기계에 다음 두 연산을 할 수 있다.
- 확장: 기계의 위쪽 끝이나 아래쪽 끝에 한 칸을 추가한다.
- 이동: 기계가 차지하는 모든 칸을 왼쪽이나 오른쪽으로 한 칸 옮긴다.
연산 후 기계가 차지하게 된 칸에 작물이 있으면 그 작물을 즉시 수확한다. 어떤 연산에서도 기계의 일부가 농장 밖으로 나갈 수 없다.
모든 작물을 수확하는 데 필요한 연산 횟수의 최솟값을 구하여라.
Input
입력은 다음과 같은 형식으로 주어진다.
각 케이스는 다음과 같은 형식으로 주어진다.
는 테스트 케이스의 수이다. 각 케이스에서 농장의 크기, 기계의 초기 위치, 작물의 수와 각 작물의 위치가 순서대로 주어진다.
Output
각 테스트 케이스마다 한 줄에 필요한 연산 횟수의 최솟값을 출력한다.
Constraints
- .
- , , .
- , .
- .
- , ().
- 기계의 초기 칸에는 작물이 없다.
- 작물의 위치는 모두 서로 다르다.
- 모든 테스트 케이스에 대한 의 합은 이하이다.
Subtasks
Samples
样例输入
2
3 4
2 1
4
2 2
3 4
1 3
2 4
2 3
1 3
2
1 1
2 2
样例输出
5
3
번 케이스에서는 확장 번과 오른쪽 이동 번으로 모든 작물을 수확할 수 있다. 번 케이스에서는 확장 번과 왼쪽 이동 번이 필요하다.