GR-O3. Qo‘shni bo‘lmagan daraxtlar

Ko‘cha bo‘ylab n ta joyga daraxt ekish mumkin; i-joyga ekilgan daraxt aᵢ foyda beradi (manfiy ham bo‘lishi mumkin). Aynan K ta daraxt ekish kerak va ikkita daraxt qo‘shni joylarda bo‘lmasligi kerak. Eng katta umumiy foyda qancha?

Kirish ma’lumotlari

Birinchi qatorda n va K, ikkinchisida n ta son.

Chiqish ma’lumotlari

Bitta son — eng katta foyda.

Cheklovlar

1 ≤ n ≤ 2·10⁵; 1 ≤ K ≤ ⌈n/2⌉; |aᵢ| ≤ 10⁹.