You are given three square grids, each of size $10^6 \times 10^6$ square cells. Each cell is labeled with $x$ and $y$ coordinates. The $x$ coordinates are numbered from $1$ to $10^6$, left to right, and the $y$ coordinates are numbered from $1$ to $10^6$, bottom to top. You must color each cell black or white.

The first grid must have the shape of a histogram rising from the bottom. In other words, if a grid cell is colored black, the cell below must also be colored black.

The second grid must have the shape of a histogram progressing from left to right. In other words, if a grid cell is colored black, the cell to the left must also be colored black.

The third grid is colored using the first two grids. If a cell $(x, y)$ is colored black in both of the first two grids, then cell $(x, y)$ in the third grid is also colored black. Otherwise, the cell is colored white. This third grid becomes your final painting.

The painting is judged by $n$ judges. Each judge will use a specific rectangular area of size $k \times 1$ for evaluation. The rectangular area used by the $i$-th judge consists of the cells $(x, y)$ where $x_i \le x \le x_i + k - 1$ and $y_i = y$. The rectangular areas do not overlap.

The $i$-th judge will reject the painting if cells $(x_i, y_i)$ and $(x_i + k - 1, y_i)$ are the same color. If the colors are different, the judge will approve the painting. The judge will award $a_i$ points if cell $(x_i, y_i)$ is white and $b_i$ points if it is black.

The painting must be approved by all judges to pass the evaluation. The painting's score is the sum of points awarded by all judges. Find the maximum possible score that can be achieved, considering all possible paintings that can pass the evaluation.

Input

The first line contains two integers $n$ and $k$ ($1 \leq n \leq 3 \cdot 10^5$, $2 \leq k \leq 10^6$).

The $i$-th of the next $n$ lines contains four integers: $x_i$, $y_i$, $a_i$, and $b_i$ ($1 \leq x_i \leq 10^6 - k + 1$, $1 \leq y_i \leq 10^6$, $1 \leq a_i, b_i \leq 10^9$). The $n$ given rectangular areas do not overlap.

Output

If there is no possible painting that can pass the evaluation, print $-1$.

Otherwise, print the maximum score that your painting can get.

Examples

Input 1

5 2
1 1 1 2
3 1 1 10
5 1 5 6
2 2 3 2
4 2 5 9

Output 1

26

Input 2

6 3
1 1 2 4
5 1 4 9
2 3 7 4
5 3 3 1
1 5 5 7
4 5 6 4

Output 2

36

Input 3

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

Output 3

51

Input 4

10 3
4 2 5 2
10 2 8 10
1 2 1 4
12 1 8 6
6 3 7 10
8 1 1 9
11 3 5 5
7 2 10 5
3 3 6 4
4 1 9 4

Output 4

72