Tenzing and Triangle

时间限制：2 秒 / 内存限制：256 MB

Description

已知在平面直角坐标系中有 $n$ 个点，其中第 $i$ 个点位于 $(x_i, y_i)$ 且权值为 $c_i$，并且有 $x_i, y_i \geq 0$，且 $x_i + y_i < k$，其中 $k$ 是一个常数。

现在，丁真同学想要删掉这 $n$ 个点，有两种删点方法：

1. 选择一个点 $i$ 删去，代价为 $c_i$。
2. 任选一个点 $(x_0, y_0)$，这个点要满足 $x_0 + y_0 < k$，且 $x_0, y_0 \geq 0$，删除所有满足 $x_i \geq x_0, y_i \geq y_0$ 的点，代价为 $l \times A$，其中 $l$ 为 $(x_0, y_0)$ 与 $x + y = k$ 的交点形成的等腰直角三角形的直角边长。

Input

• 第一行包含三个正整数 $n$ 和 $k$（$1 \leq n,k \leq 10^5$, $1 \leq A \leq 10^4$），分别表示点的数量和常数 $k,A$。
• 接下来 $n$ 行，每行包含三个整数 $x_i,y_i, c_i$（$0 \leq x_i, y_i \leq k-1$，$1 \leq c_i \leq 10^4$），分别表示第 $i$ 个点的坐标和权值。
• $x_i+y_i\leq k-1$

Output

输出一个整数，表示最小的代价。

Example

Sample Input 1

4 6 1
1 2 1
2 1 1
1 1 1
3 2 6

Sample Output 1

4

Sample Input 2

6 7 1
4 2 1
3 3 1
5 1 4
3 2 5
4 1 1
0 6 4

Sample Output 2

4

Sample Input 3

10 4 100
0 0 1
0 1 1
0 2 50
0 3 200
1 0 1
1 1 1
1 2 1
2 0 200
2 1 200
3 0 200

Sample Output 3

355