给你三个正方形网格，每个网格的大小为 $10^6 \times 10^6$ 个正方形单元格。每个单元格都用 $x$ 和 $y$ 坐标进行标记。$x$ 坐标从左到右依次编号为 $1$ 到 $10^6$，$y$ 坐标从下到上依次编号为 $1$ 到 $10^6$。你必须将每个单元格涂成黑色或白色。

第一个网格必须具有自底向上升起的直方图形状。换句话说，如果一个网格单元格被涂成黑色，那么它下方的单元格也必须被涂成黑色。

第二个网格必须具有自左向右延伸的直方图形状。换句话说，如果一个网格单元格被涂成黑色，那么它左侧的单元格也必须被涂成黑色。

第三个网格是根据前两个网格进行着色的。如果单元格 $(x, y)$ 在前两个网格中都被涂成黑色，那么第三个网格中的单元格 $(x, y)$ 也被涂成黑色。否则，该单元格被涂成白色。这第三个网格就是你最终的画作。

这幅画作将由 $n$ 位裁判进行评审。每位裁判将使用一个大小为 $k \times 1$ 的特定矩形区域进行评估。第 $i$ 位裁判使用的矩形区域由满足 $x_i \le x \le x_i + k - 1$ 且 $y_i = y$ 的单元格 $(x, y)$ 组成。这些矩形区域互不重叠。

第 $i$ 位裁判如果发现单元格 $(x_i, y_i)$ 和 $(x_i + k - 1, y_i)$ 颜色相同，将否决这幅画作。如果颜色不同，裁判将批准这幅画作。如果单元格 $(x_i, y_i)$ 为白色，裁判将给予 $a_i$ 分；如果为黑色，则给予 $b_i$ 分。

画作必须获得所有裁判的批准才能通过评估。画作的得分是所有裁判给出的分数之和。在所有能够通过评估的可能画作中，求出可以获得的最大可能得分。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 3 \cdot 10^5$，$2 \leq k \leq 10^6$）。

接下来的 $n$ 行中，第 $i$ 行包含四个整数：$x_i$、$y_i$、$a_i$ 和 $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$）。给定的 $n$ 个矩形区域互不重叠。

输出格式

如果没有能够通过评估的可能画作，输出 $-1$。

否则，输出你的画作可以获得的最大得分。

样例

输入样例 1

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

输出样例 1

26

输入样例 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

输出样例 2

36

输入样例 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

输出样例 3

51

输入样例 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

输出样例 4

72