CF301B.Yaroslav and Time

Yaroslav is playing a game called "Time". The game has a timer showing the lifespan he's got left. As soon as the timer shows 0, Yaroslav's character dies and the game ends. Also, the game has n clock stations, station number i is at point (x__i, y__i) of the plane. As the player visits station number i, he increases the current time on his timer by a__i. The stations are for one-time use only, so if the player visits some station another time, the time on his timer won't grow.

A player spends d·dist time units to move between stations, where dist is the distance the player has covered and d is some constant. The distance between stations i and j is determined as |x__i - x__j| + |y__i - y__j|.

Initially, the player is at station number 1, and the player has strictly more than zero and strictly less than one units of time. At station number 1 one unit of money can increase the time on the timer by one time unit (you can buy only integer number of time units).

Now Yaroslav is wondering, how much money he needs to get to station n. Help Yaroslav. Consider the time to buy and to increase the timer value negligibly small.

亚罗斯拉夫正在玩一款名为“时间”的游戏。游戏中有一个计时器，显示他剩余的生命时长。一旦计时器显示为 0，亚罗斯拉夫的角色即死亡，游戏结束。此外，游戏中有 $ n $ 个时钟站，第 $ i $ 号时钟站位于平面上的点 $ (x_i,,y_i) $。当玩家访问第 $ i $ 号时钟站时，其计时器当前时间将增加 $ a_i $。每个时钟站仅能使用一次；若玩家再次访问某个已访问过的时钟站，则计时器时间不会增加。

玩家在两个时钟站之间移动需消耗 $ d \cdot \text{dist} $ 个时间单位，其中 $ \text{dist} $ 表示玩家所行进的距离，$ d $ 是某个常数。时钟站 $ i $ 与 $ j $ 之间的距离定义为 $ |x_i - x_j| + |y_i - y_j| $。

初始时，玩家位于第 1 号时钟站，且其计时器时间严格大于 0、严格小于 1。在第 1 号时钟站，每花费 1 单位金钱可使计时器时间增加 1 个时间单位（仅可购买整数个时间单位）。

现在亚罗斯拉夫想知道：他至少需要花费多少金钱才能到达第 $ n $ 号时钟站？请帮助亚罗斯拉夫。假设计时器充值及购买操作所需时间可忽略不计。

The first line contains integers n and d (3 ≤ n ≤ 100, 103 ≤ d ≤ 105) — the number of stations and the constant from the statement.

The second line contains n - 2 integers: _a_2, _a_3, ..., a__n - 1 (1 ≤ a__i ≤ 103). The next n lines contain the coordinates of the stations. The i-th of them contains two integers x__i, y__i (-100 ≤ x__i, y__i ≤ 100).

It is guaranteed that no two stations are located at the same point.

第一行包含两个整数 $n$ 和 $d$（$3 \leq n \leq 100$，$10^3 \leq d \leq 10^5$）—— 分别表示车站的数量以及题目描述中的常数。

第二行包含 $n-2$ 个整数：$a_2,\,a_3,\,\dots,\,a_{n-1}$（$1 \leq a_i \leq 10^3$）。接下来的 $n$ 行给出各车站的坐标。其中第 $i$ 行包含两个整数 $x_i$、$y_i$（$-100 \leq x_i,\,y_i \leq 100$）。

保证任意两个车站均不位于同一点。

In a single line print an integer — the answer to the problem.

在一行中输出一个整数——该问题的答案。