雅罗斯拉夫正在玩一个名为“时间”的游戏。游戏有一个计时器,显示他的剩余寿命。一旦计时器显示为 0,雅罗斯拉夫的角色就会死亡,游戏结束。另外,游戏有n个时钟站,i号站位于飞机的点(xi,yi)处。当玩家访问 i 号站时,他将计时器上的当前时间增加 ai。这些站点仅供一次性使用,因此如果玩家再次访问某个站点,其计时器上的时间将不会增加。
玩家花费 d·dist 时间单位在站点之间移动,其中 dist 是玩家走过的距离,d 是某个常数。站点 i 和 j 之间的距离确定为 |xi - xj| + |yi - yj|。
最初,玩家位于 1 号站,并且玩家的时间严格大于零且严格小于 1 个单位。在1号站,一单位金钱可以将计时器上的时间增加一个时间单位(您只能购买整数个时间单位)。
现在雅罗斯拉夫想知道,他需要多少钱才能到达n站。帮助雅罗斯拉夫。考虑购买的时间并将定时器值增加到可以忽略不计的程度。
输入
第一行包含整数 n 和 d (3 ≤ n ≤ 100, 103 ≤ d ≤ 105) — 站的数量和语句中的常量。
第二行包含 n - 2 个整数:a2, a3, ..., an - 1 (1 ≤ ai ≤ 103)。接下来的 n 行包含车站的坐标。其中第 i 个包含两个整数 xi, yi (-100 ≤ xi, yi ≤ 100)。
保证没有两个站位于同一点。
输出
在一行中打印一个整数——问题的答案。
示例
输入 #1
3 1000 1000 0 0 0 1 0 3
输出 #1
2000
输入 #2
3 1000 1000 1 0 1 1 1 2
输出 #2
1000