SBG

Susu Badak Gelonggongan

Batas Waktu	1 detik
Batas Memori	32 MB
Deskripsi

Produsen susu SGM (Susu Gadjah Mada) memiliki N buah badak liar yang akan diambil susunya. Badak tersebut memiliki nomor dari 1..N. Setiap badak dapat menghasilkan susu badak sebanyak bi.

Untuk menampung susu badak liar, SGM akan membuat M buah kantong. Cara menampung susu adalah sbb:

Saat susu dari suatu badak akan diperah ke dalam kantong, badak tersebut harus diperah secara penuh (tidak boleh pindah kantong)
Saat memerah, kapasitas kantong harus mencukupi (tidak boleh ada susu tumpah)
Badak yang diperah harus urut, dari nomor 1,2,dst.
Harga yang dibutuhkan dari pembuatan kantong adalah kapasitas dari kantong yang dibuat paling besar. Bantulah SGM agar harga seminimal mungkin. Lihat deskripsi sample jika bingung.

Format Masukan

Baris 1 : 2 bilangan bulat N dan M.
Baris 2 : N buah bilangan b-i
1 <= N,M <= 10000. 1 <= bi <= 100000
Format Keluaran

Satu baris, harga terkecil yang berupa kapasitas kantong terbesar.

Contoh Masukan

5 3
1 2 3 4 5
Contoh Keluaran

6
Contoh Masukan

3 2
9 78 4
Contoh Keluaran

82
Penjelasan

Pada sample input pertama, transfer {1,2,3} ke kantong pertama, {4} ke kantong kedua, {5} ke kantong ketiga. Harga = 6 (dari kantong pertama).

Pada sample input kedua, transfer {9} ke kantong pertama, lalu {78,4} ke kantong kedua. Harga = 82 (dari kantong kedua).

Grading

20 % testcase memiliki N <= 10, M <= 2
50 % testcase memiliki N <= 10.