← 返回题目列表

Codeforces · 1842/E

E. 丹增和三角形

中文机器翻译题面 查看原题

二维平面上有 $$$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$$$。

第二个例子的图片: