C. Гукизын зам дээрх хайрцгууд

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

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

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

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

Профессор Гукизын сургууль руугаа явдаг зам дээр их хэмжээний хайрцгууд овоолж зам хаасан байв.

Зүүнээсээ баруун тийш шулуун шугамын дагуу зохион байгуулагдсан нийт $n$ ширхэг овоолго байгаа ба $i$-р ($1 ≤ i ≤ n$) овоолгод $a_{i}$ ширхэг хайрцгууд байгаа. Аз болоход түүний замаас хайрцгуудыг холдуулахад $m$ тооны оюутан туслах хүсэлтэй байгаа. Оюутнууд нэгэн зэрэг ажиллана. $0$ цагт бүх оюутнууд эхний овоолгын зүүн талд байна. Оюутан бүр энэ байрлалаасаа эхний овоолго руу шилжихэд нэг секунд шаардагддаг ба үүний дараа бүх оюутан хоёр боломжит үйлдлүүдийн дарааллыг гүйцэтгэж эхлэх ёстой, үйлдэл тус бүрийг нэг секундэд дуусгадаг. Боломжит үйлдлүүд:

  1. Хэрвээ $i ≠ n$ бол $i$-р овоолгоос $i + 1$ овоолго руу шилжинэ;
  2. Оюутнуудын байрлалд байгаа овоолго хоосон биш бол энэ овоолгоос нэг хайрцаг холдуулна.

Гукизын оюутнууд тийм ч ухаалаг биш, тиймээс та профессорыг ирэхээс өмнө хайрцгуудыг хэрхэн холдуулахыг тэдэнд хэлэх хэрэгтэй (тэр маш тэвчээргүй хүн бөгөөд, хүлээхийг хүсэхгүй байгаа). Тэд танаас Гукизын замаас бүх хайрцгыг холдуулахад шаардагдах хамгийн бага $t$ секундыг асууж байна. $t$ секундын дараа оюутнууд ямар ч байдлаар байрлаж болно, гэхдээ бүх хайрцгуудыг холдуулсан байх ёстойг анхаараарай.

Оролт

Эхний мөрөнд $n$, $m$ ($1 ≤ n, m ≤ 10^{5}$) хоёр бүхэл тоог оруулна, эдгээр нь овоолгуудын тоо болон Гукизын оюутнуудын тоо юм.

Хоёр дахь мөрөнд $n$ ширхэг $a_{1}, a_{2}, ... a_{n}$ ($0 ≤ a_{i} ≤ 10^{9}$) бүхэл тоонууд оруулах ба $a_{i}$ нь $i$-р овоолгод байгаа хайрцгуудын тоог илэрхийлнэ. Дор хаяж нэг ширхэг хоосон биш овоолго байна.

Гаралт

Нэг мөрөнд нэг тоо хэвлэнэ. Энэ нь бүх хайрцгыг холдуулахад шаардагдах хамгийн бага хугацаа (секунд) юм.

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

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

Оролт
2 1
1 1
Гаралт
4
Оролт
3 2
1 0 2
Гаралт
5
Оролт
4 100
3 4 5 4
Гаралт
5

Тэмдэглэл

Эхний жишээнд оюутан эхлээд эхний овоолго руу шилжинэ ($1$ секунд), дараа нь эхний овоолгоос хайрцгийг холдуулна ($1$ секунд), хоёр дахь овоолго руу шилжинэ ($1$ секунд) ингээд эцэст нь нэг хайрцаг холдуулна ($1$ секунд).

Хоёр дахь жишээнд оновчтой шийдлүүдийн нэг нь нэг оюутныг нэгдүгээр овоолгоос бас гуравдугаар овоолгоос хайрцаг холдуулахаар явуулна, өөр нэг оюутныг гуравдугаар овоолгоос хайрцаг холдуулахаар явуулна. Ингээд нийтдээ $5$ секунд болно.

Гурав дахь жишээнд хангалттай олон оюутнууд байгаа. Тэдний гурвыг нь эхний овоолго руу, дөрвийг нь хоёр дахь овоолго руу, тавыг нь гурав дахь овоолго руу, дөрвийг нь дөрөв дэх овоолго руу хайрцаг холдуулахаар явуулна. Үйл ажиллагаа $5$ секунд үргэлжлэх бөгөөд хамгийн сүүлийн овоолгоос хайрцгыг холдуулах үед дуусна.

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