CF301B Yaroslav and Time

Yaroslav 正在玩一款名为 “Time” 的游戏。游戏中有一个计时器，显示他还能存活的剩余时间。当计时器归零时，Yaroslav 的角色就会死亡，游戏结束。此外，游戏中有 $n$ 个时钟站，第 $i$ 个时钟站位于平面上的点 $(x_{i}, y_{i})$。每当玩家访问第 $i$ 个站时，他的计时器会增加 $a_{i}$ 的时间。每个站只能使用一次，即如果玩家再次访问某个站点，计时器不会增加时间。 玩家在站点之间移动需要消耗 $d \cdot dist$ 单位的时间，其中 $dist$ 表示玩家所走的距离，$d$ 是一个给定的常数。站点 $i$ 和 $j$ 之间的距离定义为 $|x_{i}-x_{j}|+|y_{i}-y_{j}|$。 最初，玩家位于第 1 号站点，并且他拥有严格多于 0 且严格少于 1 单位的时间。在第 1 号站点，花费 1 单位金钱可以增加计时器 1 单位时间（且只能整单位购买）。 现在 Yaroslav 想知道，他最少需要花多少钱才能到达第 $n$ 号站点。请你帮他计算。计算时可忽略购买和增加计时器的时间。

第一行包含整数 $n$ 和 $d$，表示站点数量以及常数 $d$，满足 $3 \leq n \leq 100,\ 10^3 \leq d \leq 10^5$。 第二行包含 $n-2$ 个整数：$a_{2},a_{3},...,a_{n-1}$，满足 $1 \leq a_{i} \leq 10^3$。 接下来的 $n$ 行，每行包含两个整数 $x_{i}, y_{i}$，表示每个站的坐标，$-100 \leq x_{i}, y_{i} \leq 100$。 保证没有两个站点位于同一个点。

输出一行一个整数，表示答案。

由 ChatGPT 5 翻译