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

Jerry's activity range is the interval $[0, m]$ on the number line. At the initial moment (i.e., at $t=0$ seconds), Jerry can be 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 coincides with a robotic cat (i.e., there exists a moment when their positions are exactly the same), 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.

Little 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.

Little G has designed many levels for this game and invites you to test them. To control the game difficulty, Little G plans to set a reasonable upper limit on the total cost of deploying the robotic cats. You need to help Little 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 function in your submitted source file:

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 activity range, 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 needs to 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 by the interactor no more than 20 times.

Examples

Input 1

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

The sample contains three test cases.

For the first test case, 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, when Jerry is initially at position 7 and starts moving at a constant speed of 1 unit length per second towards position 1 from the 6th second, Tom cannot successfully catch Jerry.

For the second test case, when Jerry is initially at position 5.5 and does not move, it will only coincide with the 1st robotic cat at 3.5 seconds, so deploying all robotic cats cannot win.

For the third test case, 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 point, respectively. For all test data:

• $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^3$, and for all $1 \le i \le n$, $t_i \le 10^6$. Special Property B: For all $1 \le i \le n$, $a_i \le b_i$. Special Property C: For all $1 \le i \le n$, $w_i = 0$.