三角形删点

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

二维平面上有 $n$ 个两两不同的整点和一条直线 $x+y=k$。第 $i$ 个点为 $(x_i,y_i)$，所有坐标均非负，且 $x_i+y_i<k$。

你需要删除所有点，可以任意次执行以下操作：

1. 选择非负整数 $a,b$，满足 $a+b<k$。删除由直线 $x=a$、$y=b$ 和 $x+y=k$ 围成的三角形内部及边界上的所有给定点。该等腰直角三角形的直角边长为 $k-a-b$，操作代价为 $(k-a-b)A$。
2. 选择一个尚未删除的点 $i$，只删除它，代价为 $c_i$。

求删除所有点的最小总代价。

输入格式

第一行三个整数 $n,k,A$。

接下来 $n$ 行，每行三个整数 $x_i,y_i,c_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

数据范围

• $1\le n,k\le2\times10^5$；
• $1\le A,c_i\le10^4$；
• $0\le x_i,y_i$ 且 $x_i+y_i<k$；
• 所有点的坐标两两不同。

所有测试点相互独立计分。