Chef's robot starts from the coordinate (0, 0) and wishes to reach to the coordinate (N, M).

The initial energy of the robot is 0. There are K batteries kept at some of the coordinates such that picking up the i^{th} battery costs C_{i} units, and, on picking the i^{th} battery, the current energy of the robot becomes E_{i}.

Note that one coordinate can have multiple batteries but the robot can pick at most one battery out of those.

For example, if the robot reaches a certain coordinate with energy A and there are two batteries with energy B_{1} and B_{2} on that coordinate, the robot may choose at most one battery out of these. On choosing the first battery, the energy of the robot becomes B_{1} (not A+B_{1}).

The robot can walk in all the four directions as follows:
Move up: Moving from coordinate (X, Y) to (X, Y+1), the robot loses 1 unit of energy.
Move down: Moving from coordinate (X, Y) to (X, Y-1), the robot gains 1 unit of energy.
Move right: Moving from coordinate (X, Y) to (X+1, Y), the robot loses 1 unit of energy.
Move left: Moving from coordinate (X, Y) to (X-1, Y), the robot gains 1 unit of energy.

Find the minimum cost to reach (N, M) if the robot maintains a non-negative energy throughout the journey (including the destination).

------ Input Format ------

• The first line of input contains a single integer T, the number of test cases. The description of the test cases follows.
• Each test cases consists of two lines of input.
• The first line contains three positive integers N, M, and K, the coordinates of the destination and the number of batteries.
• Next K lines have four space-separated integers each: X_{i}, Y_{i}, C_{i}, E_{i}. The i^{th} line indicates that the coordinate (X_{i}, Y_{i}) has a battery with cost C_{i} and energy E_{i}.
• The input data guarantees that the robot can reach the destination.

------ Output Format ------

For each test case, output a single integer, the minimum cost from (0,0) to (N, M).

------ Constraints ------

$1 ≤ T ≤ 10$
$1 ≤ K ≤ 10^{5}$
$0 ≤ X_{i},Y_{i} ≤ 2*10^{9}$
$1 ≤ N,M,C_{i},E_{i} ≤ 2*10^{9}$
- The sum of $K$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------
2
5 5 3
0 0 10 10
0 0 2 4
2 2 1 1
5 5 4
0 0 10 10
0 0 2 4
2 2 1 1
4 1 3 5

----- Sample Output 1 ------
10
6
----- explanation 1 ------
Test case $1$: Use the first battery with cost $10$. Thus, at coordinate $(0, 0)$, the energy of the robot becomes $10$ units. The robot can traverse the path :$(0,0) - (0, 1) - \ldots - (0, 5) - (1, 5) - \ldots - (5,5)$. It can be shown that the robot cannot reach the destination in less than $10$ units cost.

Test case $2$:
- Use the $2^{nd}$ battery: At coordinate $(0, 0)$, robot picks the $2^{nd}$ battery and the energy of the robot becomes $4$ units. The robot can move to coordinate $(2, 2)$ using this energy. On reaching $(2, 2)$, robot's energy is $0$.
- Use the $3^{rd}$ battery: At coordinate $(2, 2)$, robot picks the $3^{rd}$ battery and the energy of the robot becomes $1$ unit. The robot can move from $(2, 2)$ to $(2, 1)$ and gain $1$ unit of energy. Thus, it has $2$ units of energy now. It can now move from $(2, 1)$ to $(4, 1)$ using this energy.
- Use the $4^{th}$ battery: At coordinate $(4, 1)$, robot picks the $4^{th}$ battery and the energy of the robot becomes $5$ units. The robot can now move from $(4, 1)$ to $(5, 5)$.

见题面

见题面