← 返回题目列表

AtCoder · nadafes2022_day1_i

I. NPCA王国

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

配点 : 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