301B орчуулах · Codeforces.mn

# Яарослав ба цаг
Яарослав "Цаг" гэдэг тоглоом тоглож байна. Тоглоомд нэг цаг байх ба түүнд үлдсэн амьдрах цагийг харуулна. Цаг 0-г харуулах төдийд Яарославын баатар үхэх ба тоглоом дуусна. Мөн тоглоом $n$ цагийн зогсууртай ба $i$ дугаартай зогсуур хавтгайн $(x\_{i}, y\_{i})$ цэг дээр байрлана. Тоглогч $i$ дугаартай зогсоолд очиход тэр өөрийн цаг дээр байгаа хугацаагаа $a\_{i}$-р ихэсгэнэ. Зогсоолуудыг нэг л удаа ашиглах зориулалттай ба хэрвээ тоглогч зогсоол дээр өөр цагт очвол түүний цаг нь нэмэгдэхгүй.

Тоглогч зогсоол хооронд $d\*dist$ хугацааны нэгж зарцуулах ба энд $dist$ нь тоглогчийн туулсан зай ба $d$ нь тогтмол тоо. $i$ ба $j$ зогсоолуудын хоорондох зай нь $|x\_{i} - x\_{j}| + |y\_{i} - y\_{j}|$ байна.

Анх тоглогч $1$ дугаартай зогсоол дээр байх ба тоглогчид тэгээс эрс их ба нэгээс эрс бага хугацааны нэгж байна. $1$ дугаартай зогсоол дээр нэг нэгж мөнгөөр өөрийн цаг дээрээ нэг нэгж хугацаа нэмүүлж болно (та зөвхөн бүхэл тоон хугацааны нэгж худалдан авч болно).

Одоо Яарослав тэр $n$ зогсоолд хүрэхийн тулд түүнд хэр их мөнгө хэрэгтэй вэ гэж гайхаж байна. Яарославт туслана уу. Худалдаж авах цагийг тооцоол мөн цагийн утгыг маш бага хэмжээгээр ихэсгэ.

## Оролт
Эхний мөрөнд бүхэл тоон утгууд $n$ ба $d$ $(3 ≤ n ≤ 100, 10^{3} ≤ d ≤ 10^{5})$ байх ба зогсоолуудын тоо ба бодлогын нөхцөл дахь тогтмол юм.

Хоёр дахь мөрөнд $n - 2$ бүхэл тоон утга $a\_{2}, a\_{3}, ..., a\_{n - 1}$ $(1 ≤ a\_{i} ≤ 10^{3})$ байна. Дараагийн $n$ мөрөнд зогсоолуудын координатууд байна. $i$-р мөрөнд хоёр бүхэл тоон утга $x\_{i}$, $y\_{i}$ $($-$100 ≤ x\_{i}, y\_{i} ≤ 100)$ байна.

Ямар ч хоёр зогсоол нэг цэгт байрлахгүй нь тодорхой.

## Гаралт
Нэг мөрөнд бодлогын хариу болох бүхэл тоон утгыг хэвлэ.

-- Г.Мэндбаяр

Жишээ тэстүүд

Оролт

Гаралт

Оролт