← 返回题目列表

Codeforces · 301/B

B. 雅罗斯拉夫和时间

中文机器翻译题面 查看原题

雅罗斯拉夫正在玩一个名为“时间”的游戏。游戏有一个计时器,显示他的剩余寿命。一旦计时器显示为 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