Tenzing and Triangle

Description:

Input:

The first line of the input contains three integers $$$n$$$, $$$k$$$ and $$$A$$$ ($$$1\leq n,k\leq 2\cdot 10^5$$$, $$$1\leq A\leq 10^4$$$) — the number of points, the coefficient describing the hypotenuse of the triangle and the coefficient describing the cost of drawing a triangle.

The following $$$n$$$ lines of the input the $$$i$$$-th line contains three integers $$$x_i,y_i,c_i$$$ ($$$0\leq x_i,y_i,x_i+y_i< k$$$, $$$1\leq c_i\leq 10^4$$$) — the coordinate of the $$$i$$$-th points and the cost of erasing it using the second operation. It is guaranteed that the coordinates are pairwise distinct.

Output:

Output a single integer —the minimum cost needed to erase all of the points.

Sample Input:

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

Sample Output:

4

Sample Input:

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

Sample Output:

4

Sample Input:

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:

355

Note:

The picture of the first example:

Tenzing do the following operations:

1. draw a triangle with $$$a=3,b=2$$$, the cost $$$=1\cdot A=1$$$.
2. erase the first point, the cost $$$=1$$$.
3. erase the second point, the cost $$$=1$$$.
4. erase the third point, the cost $$$=1$$$.

The picture of the second example: