問題文

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)
• 入力はすべて整数

入力例 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