Masala #0679

Xotira 16 MB Vaqt 1000 ms

Tug’ilgan kun #6

Akrom bugun tug’ilgan kunini nishonlamoqda va shu munosabat bilan o’zining \(k\) ta do’stini kechki ovqatga taklif qildi. Kechki ovqat stolida bir qatorda terilgan \(n\) ta ovqat bo’lib, \(i\)- ovqatni yegan odamni kayfiyati \(a_i\) ga o’zgaradi. Endi Akrom bu ovqatlarni do’stlariga bo’lib berishi kerak.

Har bir mehmon stolda ketma-ket joylashgan bir nechta ovqatni yeyishi yoki umuman ovqat yemasligi ham mumkin. Ammo bitta ovqatni faqat bir kishi yeya oladi xolos. Akrom mehmonlarga ovqatlarni shunaqangi bo’lib berishi kerakki, ovqatlanib bo’lgandan so’ng mehmonlarning umumiy kayfiyati maksimal bo’lsin. Bunda Akromga yordam bering.

Kiruvchi ma'lumotlar:

Birinchi qatorda ovqatlar soni \(n\) va mehmonlar soni \(k\) kiritiladi \((1 ≤ k ≤ n ≤ 10^5)\). Keyingi qatorda \(n\) ta butun son - \(a_1, a_2, ..., a_n\) kiritiladi \((-10^9 ≤ a_i ≤ 10^9)\).

1-subtask(5 ball): \(a_i ≥ 0, n ≤ 10^5\)
2-subtask(6 ball): Ko’pi bilan bitta ovqat uchun \(a_i ≤ 0\) bo’ladi, \(n ≤ 10^5\)
3-subtask(10 ball): \(k = 1\)
4-subtask(15 ball): \(1 ≤ k ≤ n ≤ 80\)
5-subtask(26 ball): \(1 ≤ k ≤ n ≤ 2000\)
6-subtask(38 ball): \(1 ≤ k ≤ n ≤ 10^5\)

Chiquvchi ma'lumotlar:

Bitta butun son - masalaning javobini chiqaring.

Misollar

#	input.txt	output.txt
1	6 1 1 -2 3 -1 5 -6	7
2	6 2 1 2 3 -10 5 6	17
3	6 4 -1 -2 -1 0 -5 -1	0

Izoh:

Birinchi misolda yagona mehmon uchun [3, -1, 5] oraliqni bersak optimal bo’ladi.
Ikkinchi misolda 2 ta mehmonlar uchun [1, 2, 3] va [5, 6] oraliqdagi ovqatlarni bersak, ularning umumiy kayfiyati 6 + 11 = 17 bo’ladi.
Uchinchi misolda hech qaysi mehmonga ovqat bermagan ma’qul.