G. Yuk tashish jadvali

\(n\) ta konteynerdan iborat yuk qatori berilgan, ularning og'irliklari \(a_1, a_2, \dots, a_n\) massivida ko'rsatilgan.

Bu konteynerlarni ketma-ket joylashgan holda, aynan \(m\) ta yuk mashinasiga bo'lib yuklash kerak (har bir mashina konteynerlarning uzluksiz bir bo'lagini oladi, hech qanday konteyner bo'linmaydi va hech biri qoldirilmaydi).

Sizning vazifangiz — mashinalarga shunday taqsimlashni topingki, eng ko'p yuklangan mashinaning og'irligi iloji boricha kichik bo'lsin. Shu minimal qiymatni toping.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n, m\) (\(1 \le m \le n \le 2 \cdot 10^5\)) beriladi.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)) beriladi.

Chiquvchi ma'lumotlar

Yagona qatorda — eng ko'p yuklangan mashinaning minimal mumkin bo'lgan og'rligini chop eting.

Misollar

1

5 3
7 2 5 10 8

14

2

4 2
1 2 3 4

6