Masala #CSMCEBRJVY

Xotira 32 MB Vaqt 1000 ms

Maksimum Yig'indi

Koordinata tekisligida n ta nuqta mavjud. Dastlab siz x=0 nuqtada turibsiz. [1,n] oralig'ida butun nuqtalarda tangalar mavjud. Tanga manfiy qiymatga ega bo'lishi mumkin. Bir amalda ko'pi bilan k katak o'nga surilishingiz mumkin. Qaysidir nuqtaga kelganda ushbu nuqtadagi tangani olishingiz lozim. Sizning vazifangiz x=n nuqtaga maksimal qiymatdagi tangalar bilan borishdan iborat.

Kiruvchi ma'lumotlar:

Birinchi qatorda 2 ta natural son, n va k \((1<=k<=n<=10^5)\). Ikkinchi qatorda tangalarni qiymatlari beriladi, \(x_i(|x_i| \le 10^9).\)

Chiquvchi ma'lumotlar:

Yagona qatorda javobni chiqaring.

Misollar

#	input.txt	output.txt
1	4 2 1 -2 -3 3	2
2	3 1 -1 2 3	4
3	4 4 -1 -2 -3 -4	-4
4	6 4 1 2 3 4 5 6	21

Izoh:

UPD: Testlar tuzatildi.