Tom and Jerry is a well-known cartoon. Xiao G has designed a game based on this cartoon. In this game, players need to help Tom use robotic cats to catch Jerry.

Jerry's range of activity is the interval $[0, m]$ on the number line. At the initial moment (i.e., at $t=0$ seconds), Jerry may be located at any position within this interval. Afterwards, it can move freely within this interval, but its speed at any moment will not exceed 1 unit length per second.

Tom has $n$ robotic cats available for deployment, where the cost of deploying the $i$-th ($1 \le i \le n$) robotic cat is $w_i$. If the $i$-th ($1 \le i \le n$) robotic cat is deployed, it will appear at position $a_i$ at time $t_i$, then move at a constant speed of 1 unit length per second towards position $b_i$, and disappear upon arrival.

Jerry initially has $k$ health points. Whenever it completely overlaps with a robotic cat (i.e., there exists a moment when both are at the exact same position), its health points will decrease by 1, and that robotic cat will also become ineffective. When Jerry's health points are less than or equal to 0, Tom successfully catches Jerry.

Xiao G stipulates that Tom must deploy the robotic cats at the initial moment. Therefore, players need to select a number of robotic cats to deploy before the game starts. The player wins if and only if, after deploying the robotic cats, Tom can successfully catch Jerry for all possible movement paths of Jerry.

Xiao G has designed many levels for this game and invites you to test them. To control the difficulty of the game, Xiao G plans to set a reasonable upper limit on the total cost of deploying the robotic cats. You need to help Xiao G find the minimum total cost of the robotic cats required for the player to win.

Implementation Details

You do not need to, and should not, implement the main function.

You must ensure that your submitted program includes the header file game.h, i.e., add the following code at the beginning of your program:

#include "game.h"

You need to implement the following two functions in your submitted source file game.cpp:

void init(int c, int t);

• $c$ and $t$ represent the test case number and the number of test data groups, respectively. $c = 0$ indicates that this test case is a sample.
• For each test case, this function will be called exactly once by the interaction library when the program starts running.

long long game(int n, int m, int k, std::vector<int> a,
std::vector<int> b, std::vector<int> t, std::vector<int> w);

• $n, m, k$ represent the number of robotic cats, Jerry's range of activity, and Jerry's initial health points, respectively.
• For $0 \le i < n$, $a_i, b_i, t_i, w_i$ represent the appearance position, final position, appearance time, and deployment cost of the $i+1$-th robotic cat, respectively.
• This function should return the minimum total cost. Specifically, if it is impossible to win even by deploying all robotic cats, return $-1$.
• For each test case, this function will be called exactly $t$ times by the interaction library.

Note: In any case, the time required for the interaction library to run will not exceed 0.1 seconds, and the memory used is fixed and will not exceed 64 MiB.

Testing Procedure

The grader.cpp in the problem directory is a reference implementation of the interaction library. The interaction library used for final testing is different from this reference implementation, so the player's solution should not rely on the implementation of the interaction library.

Players can compile the executable program in the problem directory using the following command:

g++ grader.cpp game.cpp -o game -O2 -std=c++14 -static

For the compiled executable: The executable will read data in the following format from standard input: The first line of input contains two non-negative integers $c, t$, representing the test case number and the number of test data groups. Following this are the test data for each group. For each group of test data: The first line contains three positive integers $n, m, k$, representing the number of robotic cats, Jerry's range of activity, and Jerry's initial health points. The $i+1$-th line ($1 \le i \le n$) contains four non-negative integers $a_i, b_i, t_i, w_i$, representing the appearance position, final position, appearance time, and deployment cost of the $i$-th robotic cat. The executable will output data in the following format to standard output: * For each group of test data, output a single integer representing the minimum total cost. Specifically, if it is impossible to win even by deploying all robotic cats, output $-1$.

Examples

Input 1

1 0 3
4 10 1
0 6 0 1
4 8 6 2
10 2 7 3
0 8 4 4
3 6 2
2 6 0 0
4 0 1 0
5 0 2 0
7 9 2
3 0 1 7
3 6 1 8
6 9 4 9
3 0 7 3
3 6 7 3
3 6 7 5
6 9 10 5

Output 1

6
-1
35

Note 1

The sample contains three groups of test data. For the first group, the player can choose to deploy the 1st, 2nd, and 3rd robotic cats, with a total cost of $1+2+3 = 6$. If the player chooses to deploy the 1st and 3rd robotic cats, then when Jerry is initially at position 7 and moves at a constant speed of 1 unit length per second from $t=6$ seconds towards position 1, Tom cannot successfully catch Jerry. For the second group, when Jerry is initially at position 5.5 and does not move, it will only completely overlap with the 1st robotic cat at $t=3.5$ seconds, so deploying all robotic cats will not result in a win. For the third group, the player can choose to deploy the 1st, 2nd, 3rd, 4th, 5th, and 7th robotic cats, with a total cost of $7 + 8 + 9 + 3 + 3 + 5 = 35$.

Constraints

Let $N$ and $S$ be the sum of $n$ and $nk$ for all test data in a single test case, respectively. For all test data: $1 \le t \le 20$; $1 \le n \le 5 \times 10^4$, $N \le 3 \times 10^5$; $1 \le m \le 10^9$, $1 \le k \le 10$, $S \le 10^6$; For all $1 \le i \le n$, $0 \le a_i, b_i \le m$, $0 \le t_i, w_i \le 10^9$.

Special Property A: $m \le 10$, and for all $1 \le i \le n$, $t_i, w_i \le 10$. Special Property B: $m \le 10^3$, and for all $1 \le i \le n$, $t_i \le 10^6$. Special Property C: For all $1 \le i \le n$, $w_i = 0$. Special Property D: For all $1 \le i \le n$, $a_i \le b_i$.

Scoring

• Players should not obtain internal information of the interaction library through illegal means, such as directly interacting with standard input/output streams. Such behavior will be considered cheating.
• The final evaluation interaction library is different from the sample interaction library.
• This problem is subject to the same restrictions as traditional problems; for example, compilation errors will result in 0 points for the entire problem, and runtime errors, time limit exceeded, or memory limit exceeded will result in 0 points for the corresponding test case. Players can only access variables defined in their own program and variables provided by the interaction library; attempting to access other address spaces may lead to compilation or runtime errors.
• Based on the above conditions: For each test case, the program receives full marks if and only if the answer returned by each call to the game function is correct.