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)$.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Shortest paths

Sorting

Range queries

Segment trees revisited

Data structures


Solutions:
from bisect import bisect
from math import inf
from operator import itemgetter
import sys
cin = sys.stdin
r = cin.readline
ri = lambda : range(int(r()))
mi = lambda : map(int, r().split())
for _ in ri():
	(n, m, k) = mi()
	final = n + m
	xyce = [tuple(mi()) for _ in range(k)]
	batteries = [(x + y, c, e) for (x, y, c, e) in xyce if x + y < final]
	batteries.sort(key=itemgetter(0))
	dp = [(-final, 0)]
	for (loc, c, e) in reversed(batteries):
		j = bisect(dp, (-(loc + e), -inf))
		if j == len(dp):
			continue
		dpval = c + dp[j][1]
		while dpval < dp[-1][1]:
			dp.pop()
		if loc != dp[-1][0]:
			dp.append((-loc, dpval))
	print(dp[-1][1])


from bisect import bisect
from math import inf
from operator import itemgetter
import sys
cin = sys.stdin
read = cin.readline
rir = lambda : range(int(read()))
mir = lambda : map(int, read().split())
for _ in rir():
	(n, m, k) = mir()
	final = n + m
	xyce = [tuple(mir()) for _ in range(k)]
	batteries = [(x + y, c, e) for (x, y, c, e) in xyce]
	batteries = [b for b in batteries if b[0] < final]
	batteries.sort(key=itemgetter(0))
	batteries.append((final, 0, 0))
	dp = [(-final, 0)]
	for (loc, c, e) in reversed(batteries):
		if loc == final:
			continue
		j = bisect(dp, (-(loc + e), -inf))
		if j == len(dp):
			continue
		dpval = c + dp[j][1]
		while dpval < dp[-1][1]:
			dp.pop()
		dp.append((-loc, dpval))
	res = min((cost for (loc, cost) in dp if loc == 0))
	print(res)