CF1842E.Tenzing and Triangle

There are $n$ pairwise-distinct points and a line $x+y=k$ on a two-dimensional plane. The $i$-th point is at $(x_i,y_i)$. All points have non-negative coordinates and are strictly below the line. Alternatively, $0 \leq x_i,y_i, x_i+y_i \lt k$.

Tenzing wants to erase all the points. He can perform the following two operations:

1. Draw triangle: Tenzing will choose two non-negative integers $a$, $b$ that satisfy $a+b \lt k$, then all points inside the triangle formed by lines $x=a$, $y=b$ and $x+y=k$ will be erased. It can be shown that this triangle is an isosceles right triangle. Let the side lengths of the triangle be $l$, $l$ and $\sqrt 2 l$ respectively. Then, the cost of this operation is $l \cdot A$.

   The blue area of the following picture describes the triangle with $a=1,b=1$ with cost $=1\cdot A$.

   

2. Erase a specific point: Tenzing will choose an integer $i$ that satisfies $1 \leq i \leq n$ and erase the point $i$. The cost of this operation is $c_i$.

Help Tenzing find the minimum cost to erase all of the points.

平面上有 $n$ 个两两互异的点，以及一条直线 $x+y=k$。第 $i$ 个点位于 $(x_i,y_i)$。所有点的坐标均为非负数，且严格位于该直线下方，即满足 $0 \leq x_i, y_i$ 且 $x_i + y_i < k$。

登真希望擦除所有这些点。他可以执行以下两种操作：

1. 绘制三角形：登真选择两个非负整数 $a$、$b$，满足 $a + b < k$，然后擦除由直线 $x = a$、$y = b$ 和 $x + y = k$ 所围成的三角形内部的所有点。可以证明，该三角形是一个等腰直角三角形。设该三角形的两条直角边长均为 $l$，斜边长为 $\sqrt{2}\,l$，则该操作的代价为 $l \cdot A$。

   下图中蓝色区域表示当 $a = 1$、$b = 1$ 时对应的三角形，其代价为 $1 \cdot A$。

   

2. 擦除特定点：登真选择一个满足 $1 \leq i \leq n$ 的整数 $i$，擦除第 $i$ 个点。该操作的代价为 $c_i$。

请帮助登真求出擦除所有点所需的最小总代价。

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 \lt 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.

输入的第一行包含三个整数 $n$、$k$ 和 $A$（$1\leq n,k\leq 2\cdot 10^5$，$1\leq A\leq 10^4$）——分别表示点的数量、描述三角形斜边的系数，以及绘制一个三角形的代价系数。

接下来的 $n$ 行中，第 $i$ 行包含三个整数 $x_i,y_i,c_i$（$0\leq x_i,y_i,x_i+y_i \lt k$，$1\leq c_i\leq 10^4$）——表示第 $i$ 个点的坐标及其使用第二种操作擦除该点的代价。保证所有坐标的两两互不相同。

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

输出一个整数——擦除所有点所需的最小代价。

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:

第一个示例的图示：

丹增执行以下操作：

1. 绘制一个边长为 $a=3$、$b=2$ 的三角形，花费 $=1\cdot A=1$。
2. 擦除第一个点，花费 $=1$。
3. 擦除第二个点，花费 $=1$。
4. 擦除第三个点，花费 $=1$。

第二个示例的图示：