B. Онгоцны буудал

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

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

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

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

Лолек, Болек хоёр онгоцоор явах гэж байна. Онгоцны буудал дээр "Онгоцоо сонго" нэртэй урашмуулалт хөтөлбөр зарлагджээ. Энэ нь дараах дүрэмтэй:

  • Зорчигч хүссэн онгоцоо сонгож болно
  • Билет авах үед онгоцонд $x$ ($x > 0$) хоосон суудал байвал зорчигч билетийг $x$ злотоор (Польшийн мөнгөний нэгж) худалдан авна.

Яг одоо онгоцны буудлын кассан дээр $n$ хүн оочирлож байгаа. Лолек, Болек хоёр дараалалд зогсоогүй байгаа ч онгоцны буудлынхан $n$ билет зарахад хамгийн ихдээ болон хамгийн багадаа хэдэн злотын билет зарах боломжтойг сонирхож байгаа.

Дарааллын эхэнд зогсож байгаа хүн билетээ авсны дараа хоёрдугаар хүн билетээ авна гэх мэтээр $n$-р хүн билетээ авах хүртэл дараалал үргэлжилдэг.

Оролт

Эхний мөрөнд дараалалд байгаа хүний тоо $n$ болон нислэгийн тоо $m$ ($1 ≤ n, m ≤ 1000$) өгөгдөнө. Дараагийн мөрөнд $a_1, a_2, ... , a_m$ ($1 ≤ a_i ≤ 1000$) болох нийт $m$ тоо байна. Энд $a_i$ нь билет зарж эхлэх үед $i$-р онгоцонд байгаа сул суудлын тоог илэрхийлнэ.

Анх багадаа $n$ ширхэг хоосон суудал байна.

Гаралт

Олж болох хамгийн их болон хамгийн бага орлогын хэмжээ болох хоёр тоог зайгаар тусгаарлан хэвлэ.

Орчуулсан: zoloogg

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

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

Тэмдэглэл

In the first test sample the number of passengers is equal to the number of empty seats, so regardless of the way the planes are chosen, the administration will earn the same sum.

In the second sample the sum is maximized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person -- to the 2-nd plane, the 3-rd person -- to the 3-rd plane, the 4-th person -- to the 1-st plane. The sum is minimized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person -- to the 1-st plane, the 3-rd person -- to the 2-nd plane, the 4-th person -- to the 2-nd plane.

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