A. Хөгшин Пэекэн

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

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

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

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

Хөгшин Пэекэний амьдардаг улсад $n$ тооны хот байдаг. Эдгээр хотууд нь зүүнээс баруун тийш шулуун шугамын дагуу байрладаг ба бид $c_{1}, c_{2}, ..., c_{n}$ гэж илэрхийлнэ. Мөн $(n - 1)$ ширхэг нэг урсгалтай замууд байдаг. $i$-р зам нь $c_{i}$ хотоос $c_{i + 1}$ хотруу хүрдэг бөгөөд $d_{i}$ километрийн урттай байна.

Хөгшин Пэекэн $1$ цагт $1$ километр аялдаг ба энэ хугацаандаа $1$ литр шатахуун хэрэглэдэг.

$c_{i}$ (сүүлийн $c_{n}$ хотоос бусад) хот бүрд $s_{i}$ литр шатахууны хангамж байдаг ба хэрвээ Хөгшин Пэекэн энэ хотоор дайрч өнгөрвөл, эсвэл энэ хотод ирвэл тэр даруй шатахууны хангамжийг Пэекэнд өгдөг. Энэхүү шатахууны хангамж $k$ цагийн дараа дахин бий болдог. Хөгшин Пэекэн аль нэг хотод байх хугацаандаа хэдэн ч удаа шатахуун авч болно.

Эхлээд (цаг $0$ байхад) Хөгшин Пэекэн $c_{1}$ хотод байх ба түүний шатахууны сав руу $s_{1}$ литр шатахуун хийнэ. Түүний шатахууны сав хязгааргүй багтаамжтай. Хэрвээ хоёр хотын дунд Хөгшин Пэекэний шатахуун дуусвал тэр аялалаа цааш үргэлжлүүлж чадахгүйд хүрнэ.

Хөгшин Пэекэн $c_{n}$ хотод очтол хамгийн багадаа хэдэн цаг зарцуулах вэ?

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан $m$ ба $k$ $(1 ≤ m, k ≤ 1000)$ бүхэл тоонууд байна. $m$ утга нь хотуудын хоорондох замын тоог илэрхийлэх бөгөөд $(n - 1)$-тэй тэнцүү байна.

Дараагийн мөрөнд зайгаар тусгаарлагдсан $m$ ширхэг $d_{1}, d_{2}, ..., d_{m}$ $(1 ≤ d_{i} ≤ 1000)$ бүхэл тооууд байх ба түүний дараагийн мөрөнд мөн зайгаар тусгаарлагдсан $m$ ширхэг $s_{1}, s_{2}, ..., s_{m}$ $(1 ≤ s_{i} ≤ 1000)$ бүхэл тоонууд байна.

Гаралт

Хөгшин Пэекэн $c_{1}$ хотоос $c_{n}$ хот хүртэл зарцуулах хамгийн бага хугацаа болох нэг бүхэл тоо агуулсан нэг мөр хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
4 6
1 2 5 2
2 3 3 4
Гаралт
10
Оролт
2 3
5 6
5 5
Гаралт
14

Тэмдэглэл

Хоёр дахь жишээнд Хөгшин Пэекэн $c_{1}$ хотод $3$ цаг саатна.

Сэтгэгдлүүдийг ачааллаж байна...