Problem : 200 - SETNJA

Problem Statistics

Solved Member: 3　　Submission: 6　　User Tried: 4

Statement:

Mirko 大大想要帶他的朋友們去一場將在 Zagreb 舉行的 "Zaz" 演唱會。他已經拿到足夠的票了，因此他現在正在他家附近散步，順便將票分給他的朋友們。

Mirko 家附近可以用一個笛卡爾坐標系來表示。當 Mirko 大大在走路的時候，他只會踩在格子點上〈即x, y座標均為整數〉。他走路時有八個方向，分別是上下左右和對角四方位。

Mirko 的每位朋友也都住在格子點上，並且他們會走到他們家附近和 Mirko 會面。Mirko 只能和朋友在格子點上會面，而且因為每個朋友都有屬於自己的懶惰程度 P，因此只能在離每位朋友家 P 步的距離碰面。

Mirko 回家之後，他記得他拜訪朋友們的順序，請你依照這個順序計算出他所需要走的步數最小值為多少。

請注意，Mirko 的起點和終點是未知的。

Input:Output:

第一行有一個整數 N(2 ≤ N ≤ 200 000)，代表 Mirko 的朋友數量。

接下來有 N 行，每行有三個整數，分別代表這位朋友家的 x, y 座標和懶惰程度 P。

這N行資訊依照 Mirko 的拜訪順序排序。

請輸出唯一一行，代表 Mirko 完成他的任務所需要走的最少步數。

Sample Input:Sample Output:

SAMPLE A:
3
3 10 2
8 4 2
2 5 2

SAMPLE B:
4
3 3 5
7 11 5
20 8 10
30 18 3

SAMPLE A:
4

SAMPLE B:
19

HINT:

占分 30% 的測資裡，N 最大值為 200。
另外 30% 的測資，P 不會超過 10。

第一筆範例測資中，Mirko 從 (4, 8) 碰到他的第一個朋友，並在 (6, 6) 碰到第二個朋友，並在 (4, 5) 碰到他的第三個朋友。

Source:

COI 2012

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	3000ms	262144kb
0-2	3000ms	262144kb
1	3000ms	262144kb	10
2	3000ms	262144kb	10
3	3000ms	262144kb	10
4	3000ms	262144kb	10
5	3000ms	262144kb	10
6	3000ms	262144kb	10
7	3000ms	262144kb	10
8	3000ms	262144kb	10
9	3000ms	262144kb	10
10	3000ms	262144kb	10