B. Яарослав ба цаг

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Яарослав "Цаг" гэдэг тоглоом тоглож байна. Тоглоомд нэг цаг байх ба түүнд үлдсэн амьдрах цагийг харуулна. Цаг 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)$ байна.

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

Гаралт

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

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 1000
1000
0 0
0 1
0 3
Гаралт
2000
Оролт
3 1000
1000
1 0
1 1
1 2
Гаралт
1000
Сэтгэгдлүүдийг ачааллаж байна...