B. Ухаан муутай залуу Деву

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

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

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

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

Деву бол ухаан муутай залуу ба тэр суралцахдаа маш удаан. Та түүнд $n$ хичээл заана гэж үзье, $i$-р хичээл $c_{i}$ бүлэгтэй. Та хичээлүүдийг заахдаа хичээлүүдийн бүх бүлгийг үргэлжлүүлэн заана.

Девугийн эхний хичээлийн нэг бүлгийг суралцах чадвар нь $x$ цаг. Өөрөөр хэлбэл тэр тухайн хичээлийн бүлгийг $x$ цагт сурна гэсэн үг.

Деву бас тийм ч ухаан муутай биш ба түүний талаар сайн мэдээ ч бас байна. Хэрвээ та түүнд хичээл заах юм бол дараагийн хичээлийн дурын бүлгийг заахад шаардлагатай цаг нь өмнө шаардлагатай байснаасаа 1 цагаар бага байна (илүү тодорхой ойлгохын тулд жишээнүүдийг харна уу). Девугийн нэг бүлгийг суралцах чадвар нь 1 цагаас бага байхгүй.

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

Хариулт 32 битийн өгөгдлийн төрөлд таарахгүй байж болох тул болгоомжтой байна уу.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $n$, $x$ ($1 ≤ n, x ≤ 10^{5}$) байна. Дараагийн мөрөнд зайгаар тусгаарлагдсан $n$ бүхэл тоо $c_{1}, c_{2}, ..., c_{n}$ ($1 ≤ c_{i} ≤ 10^{5}$) байна.

Гаралт

Бодлогын хариуг илэрхийлэх нэг бүхэл тоог хэвлэ.

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

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

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

Тэмдэглэл

Эхний жишээг авч үзье. Хичээлүүдийн дарааллыг: $1$, $2$ гэе. Та Девуд эхний хичээлийг заах үед түүнд бүлэг тус бүрт $3$ цаг зарцуулах ба эхний хичээлийг заахад нийт $12$ цаг зарцуулна. Эхний хичээлийг заасны дараа түүнд нэг бүлгийг заах хугацаа $2$ цаг болно. Одоо түүнд хоёрдугаар хичээлийг заах ба үүнд $2 × 1 = 2$ цаг зарцуулна. Ингэснээр та нийт $12 + 2 = 14$ цаг зарцуулна.

Хичээлүүдийн дарааллыг $2$, $1$ гэе. Та Девуд хоёрдугаар хичээлийг заах үед бүлэг бүрт $3$ цаг зарцуулах ба нийт $3 × 1 = 3$ цаг зарцуулна. Хоёрдугаар хичээлийг заасны дараа түүний нэг бүлгийг сурах хугацаа $2$ цаг болно. Одоо түүнд эхний хичээлийг заахад $2 × 4 = 8$ цаг зарцууна. Ингээд танд нийтдээ $11$ цаг хэрэгтэй.

Хоёр тохиолдлын хувьд хамгийн бага цаг нь $11$ цаг.

Гуравдугаар жишээг харцгаая. Энэ жишээн дээр хичээлүүдийн дараалал ямар ч хамаагүй. Та Девуд эхний хичээлийг заах үед түүнд бүлэг тус бүрт $3$ цаг зарцуулна. Та Девуд хоёрдугаар хичээлийг заах үед бүлэг бүрт $2$ цаг зарцуулна. Та Девуд гуравдугаар хичээлийг заах үед бүлэг бүрт $1$ цаг зарцуулна. Ингээд нийтдээ $6$ цаг зарцуулна.

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