二维平面上有 $$$n$$$ 成对的不同点和一条线 $$$x+y=k$$$。第 $$$i$$$ 个点位于 $$$(x_i,y_i)$$$。所有点都有非负坐标并且严格位于线下方。或者,$$$0 \leq x_i,y_i, x_i+y_i < k$$$。
Tenzing 想要删除所有点。他可以执行以下两个操作:
1.绘制三角形:Tenzing会选择两个满足$$$a+b<k$$$的非负整数$$$a$$$、$$$b$$$,则$$$x=a$$$、$$$y=b$$$和$$$x+y=k$$$构成的三角形内的所有点将被擦除。可以证明这个三角形是等腰直角三角形。设三角形的边长分别为$$$l$$$、$$$l$$$ 和$$$\sqrt 2 l$$$。那么,这个操作的成本就是$$$l \cdot A$$$。下图的蓝色区域描述了$$$a=1,b=1$$$的三角形,成本为$$$=1\cdot A$$$。
2.擦除特定点:Tenzing将选择一个满足$$$1 \leq i \leq n$$$的整数$$$i$$$并擦除点$$$i$$$。此操作的成本为$$$c_i$$$。
帮助 Tenzing 找到消除所有点的最小成本。
输入
输入的第一行包含三个整数 $$$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< k$$$, $$$1\leq c_i\leq 10^4$$$) — 坐标$$$i$$$ 个点以及使用第二次操作擦除它的成本。保证坐标是两两不同的。
输出
输出一个整数——擦除所有点所需的最小成本。
示例
输入 #1
4 6 1 1 2 1 2 1 1 1 1 1 3 2 6
输出 #1
4
输入 #2
6 7 1 4 2 1 3 3 1 5 1 4 3 2 5 4 1 1 0 6 4
输出 #2
4
输入 #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
输出 #3
355
注意
第一个例子的图片:
Tenzing 执行以下操作:
1. 画一个三角形$$$a=3,b=2$$$,成本$$$=1\cdot A=1$$$。
2.擦除第一个点,成本$$$=1$$$。
3.擦除第二个点,成本$$$=1$$$。
4.删除第三点,成本$$$=1$$$。
第二个例子的图片: