Cheap Airlines

Bajtazar is finally taking a long-awaited holiday, which he plans to spend soaking up the sun on the golden sands of the Bitocki Sea. Weighing his biorhythm, the weather forecast, and the cultural events of Bitocja, Bajtazar assigns to each of the $n$ holiday days a recreation coefficient: an integer that says how much fun he would have that day. Each coefficient is an integer and may be negative, which means that on that day Bajtazar would rather stay home and weed his garden.

Luckily, Bajtazar does not have to spend the whole holiday by the sea. His favorite cheap airline is running a promotion that lets him buy up to $k$ plane tickets at an unusually attractive price (each ticket covers one round trip to the Bitocki Sea and back).

Help Bajtazar plan the holiday so that the sum of the recreation coefficients over the days he spends by the sea is as large as possible, given that he may fly to the sea at most $k$ times. Assume the planes fly at night, so a single trip covers a block of consecutive days by the sea. In other words, the days spent by the sea form at most $k$ non-overlapping intervals of consecutive days, and taking no trip at all (a sum of $0$) is allowed.

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 1{,}000{,}000$). The second line contains $n$ integers, each with absolute value at most $10^9$, describing the recreation coefficients of the consecutive holiday days.

Print a single integer: the sum of recreation coefficients in an optimal holiday plan.