Trong trò chơi Move2Win, người chơi sẽ được đưa vào một bản đồ được chia thành các ô vuông đơn vị. Có ~ n-2 ~ ô vuông trên bản đồ được đặt phần thưởng, ô vuông thứ ~ i ~ ~ (i = 2..n-1) ~ có tọa độ ~ (x_i, y_i) ~ với phần thưởng là một bình năng lượng có giá trị ~ a_i ~ . Nhiệm vụ của người chơi là phải di chuyển từ ô ~ (x_1, y_1) ~ đến ô thứ ~ (x_n, y_n) ~ sao cho năng lượng của người chơi luôn lớn hơn hoặc bằng 0. Biết rằng:

Người chơi có thể di chuyển từ ô ~ (x,y) ~ đến ô ~ (u,v) ~ với chi phí năng lượng là ~ d(|x-u|+|y-v|) ~, trong đó ~ d ~ là một hằng số cho trước. Nếu người chơi di chuyển đến ô ~ (u,v) ~ chứa phần thưởng thì năng lượng của người chơi được tăng lên một lượng đúng bằng năng lượng của phần tưởng tại ô đó. Mỗi phần thưởng chỉ được sử dụng tối đa một lần.

**Yêu cầu: ** Hãy xác định năng lượng ít nhất của người chơi có tại ô xuất phát để người chơi đi chuyển được đến ô đích.

Dữ liệu vào

• Dòng đầu tiên ghi lần lượt hai số nguyên dương ~ n,d ~;
• Dòng thứ 2 chứa ~ n-2 ~ số nguyên lần lượt là ~ a_2, a_3, …, a_{n-1} ~;
• ~ i ~ ~ (i = 1…n) ~ dòng tiếp theo, dòng thứ ~ i ~ chứa hai số nguyên ~ x_i, y_i ~ cho biết tọa độ của một ô, trong đó ô ~ (x_1, y_1) ~ là ô xuất phát, ô ~ (x_n, y_n) ~ là ô đích, các ô còn lại chứa phần thưởng.

Kết quả

• Ghi một số nguyên duy nhất là kết quả của bài tóan.

Ràng buộc

• ~ 2 ≤ n ≤ 100 ~;
• ~ 10^3 ≤ d ≤ 10^5 ~
• ~ -100 ≤ x_i, y_i ≤ 100 ~
• ~ 1 ≤ a_i ≤ 10^3 ~

Ví dụ:

Input 1

3 1000
1000
0 0
0 1
0 3 

Output 1

2000