# Rocket Pack CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

Rocket Pack CodeChef Solution

## Rocket Pack CodeChef Solution ## Problem

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 \leq T \leq 10
• 1 \leq K \leq 10^5
• 0 \leq X_i,Y_i \leq 2*10^9
• 1 \leq N,M,C_i,E_i \leq 2*10^9
• The sum of K over all test cases won’t exceed 10^5.

### Sample 1:

Input

Output

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

10
6

### Explanation:

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). ## Rocket Pack CodeChef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW 