配点 : 500 点
問題文
NPCA王国是 维度平面上的 2 由 N 城镇组成, i\,(1 \leq i \leq N) 的坐标是 (x_i,y_i) 。
当且仅当以下条件成立时,该镇 两个方向的连接长度 i 和镇 j 有一条 c_i+c_j 路径。
- \min(|x_i-x_j|,|y_i-y_j|) \leq K
町 1 卡拉町 找到到 N 的最短距离。
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 0 \leq x_i,y_i,c_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j)\,(i \neq j)
- 输入全部为整数
入力
输入是按以下格式从标准输入给出的。
N K x_1 y_1 c_1 x_2 y_2 c_2 \vdots x_N y_N c_N
出力
打印答案。然而,小镇 1 卡拉町
找到到 N ,
连接长度-1 。
入力例 1
3 3 1 3 10 3 10 5 7 13 5
出力例 1
25
町 1 和镇 2 领带长度 15 道路和城镇 2 和镇 3 领带长度 10 路径。\min(|x_1-x_3|,|y_1-y_3|) = 6 > 3 所以小镇 没有路径连接 1 和镇 3 。
入力例 2
2 1 1 1 10 10 10 10
出力例 2
-1
入力例 3
6 100 105 203 115 56 51 299 47 85 234 108 277 160 260 237 25 170 147 127
出力例 3
242