题目描述

Feudalia 与 Banania 的最终决战即将开始。在 Feudalia 的军队抵达 Banania 首都之前，他们必须穿过一块宽为 $W$、高为 $H$ 的区域，并且不能被任何雷达探测到。

区域左右两侧各有一堵可以视为无限延伸的墙，分别经过 $(0,0)$、$(0,H)$ 和 $(W,0)$、$(W,H)$。军队需要从区域的下边界到达上边界，途中不能穿过这两堵墙。

区域内共有 $N$ 个雷达。第 $i$ 个雷达位于 $(x_i,y_i)$，其初始功率为 $p_i$。雷达的功率必须是非负整数，同时它的功耗就等于当前功率。

若某个雷达当前功率为 $P$，则它的探测半径为 $P^2$。也就是说，所有与该雷达中心的欧氏距离不超过 $P^2$ 的点都会被探测到。

Feudalia 的军队需要找到一条从下边界到上边界的路径。形式化地说，需要存在一条连接某个点 $(x_0,0)$ 与某个点 $(x_1,H)$ 的曲线，这条曲线不能穿过左右两侧的墙，并且对于路径上的任意一点 $(x,y)$ 以及任意一个雷达，其到该雷达中心的距离都必须严格大于该雷达当前的探测半径。

你是一名 Feudalia 间谍，可以破坏雷达并降低其功率。对于每个雷达，你可以把它的功率修改为任意一个不超过其初始功率的非负整数，但不能提高功率。

请调整各个雷达的功率，使得军队能够安全穿过这片区域。为了尽可能不引起注意，你希望总功耗的减少量最小。

求至少需要减少多少总功耗。

输入格式

第一行输入三个整数 $N,W,H$，分别表示雷达数量以及区域的宽和高。

接下来 $N$ 行，第 $i$ 行输入三个整数 $x_i,y_i,p_i$，表示第 $i$ 个雷达的位置和初始功率。

输出格式

输出一个整数，表示为了使军队能够从下边界安全到达上边界，所需的最小总功耗减少量。

输入输出样例 #1

输入 #1

1 8 20
4 4 10

输出 #1

9

输入输出样例 #2

输入 #2

3 3 5
1 1 1
1 2 1
2 2 1

输出 #2

1

输入输出样例 #3

输入 #3

3 6 16
1 8 2
3 8 2
5 8 2

输出 #3

3

输入输出样例 #4

输入 #4

2 51 4
46 2 8
8 1 8

输出 #4

8

输入输出样例 #5

输入 #5

5 24 32
3 18 2
6 23 2
10 10 2
18 13 3
13 26 1

输出 #5

0

输入输出样例 #6

输入 #6

9 20 30
1 5 5
1 10 4
5 4 3
5 11 5
15 3 4
15 9 3
19 1 2
19 8 2
19 17 2

输出 #6

10

样例说明

对于样例 #1，唯一一个雷达的初始功率为 $10$。如果将其功率降为 $1$，探测半径变为 $1$，此时军队可以通过，因此总功耗减少量为 $10-1=9$。如果只将功率降为 $2$，探测半径仍有 $4$，军队无法通过。

对于样例 #2，只需要关闭第三个雷达，即可出现一条安全路径。

对于样例 #3，一种最优方案是把第一个雷达的功率降为 $0$，把第二个雷达的功率降为 $1$，第三个雷达保持不变，总功耗减少量为 $3$。

对于样例 #5，初始状态下已经存在安全路径，因此无需降低任何雷达的功率，答案为 $0$。注意，安全路径不一定是直线。

数据范围与约定

• $1\le N\le 30$；
• $3\le W,H\le 1000$；
• $1\le x_i\le W-1$；
• $1\le y_i\le H-1$；
• $1\le p_i\le 200$；
• 任意两个雷达的位置不同。