Harvest

문제 정보

문제

Farmer John has an apple farm. As the harvesting season approaches, he is planning for harvesting the apples. The farm is formed as a rectangular grid with N rows and M columns. Each grid cell may have an apple tree in it.

Farmer John will start at the top-left cell of the farm, and drive a cultivator to collect the apples. Unfortunately, the cultivator is quite old and has some problems - for one thing, it can only move in two directions: down and right. In other words, if the cultivator is located at (i, j), it can either go to (i + 1, j) or (i, j + 1).
FJ wants a single trip on his cultivator which can collect the most apples possible. Write a program to find a path with maximum apple trees.

입력

Your program is to read from standard input. The input consists of T test cases. The number of test cases T (1 <= T <= 100) is given in the first line of the input. In the first line of each case, 3 integers N,M,K(1 <= N,M <= 2147483647, 1 <= K <= 20000) will be given.In the next K lines, the location of each apple tree yi, xi will be given (1 <= yi <= N, 1 <= xi <= M). You can assume no cell contains more than one tree.

출력

Your program is to write to standard output. Print exactly one line for each test case, containing the maximum number of apple trees Farmer John can visit.

예제 입력

2
3 3 2
1 1
3 3
5 5 10
1 1
1 2
1 3
1 4
1 5
2 1
2 5
3 5
4 5
5 5

예제 출력

2
9

노트

1개의 댓글이 있습니다.