Mowing the Lawn

A year ago Farmer John won the town's annual best-lawn competition, and he has been lazy ever since: he has not mowed his lawn once, so it has grown completely unruly. The competition is coming up again soon, and FJ wants to whip his lawn back into top shape so he can reclaim the title.

The lawn is so overgrown that FJ cannot handle it alone; he needs help from his $N$ cows ($1 \le N \le 100{,}000$), who stand in a single row numbered $1$ through $N$ from left to right. Some cows mow more efficiently than others: cow $i$ has efficiency $E_i$ ($0 \le E_i \le 1{,}000{,}000{,}000$).

FJ has noticed that cows standing close together in the row are good friends: if he picks more than $K$ ($1 \le K \le N$) consecutive (adjacent) cows, they will ignore the lawn and throw a party instead. Determine the largest total efficiency FJ can obtain without ever choosing more than $K$ consecutive cows.

• Line 1: Two space-separated integers, $N$ and $K$.
• Lines 2 through $N+1$: Line $i+1$ contains the single integer $E_i$.

• Line 1: A single integer, the best total efficiency FJ can obtain.

Suppose there are $5$ cows with efficiencies $1, 2, 3, 4, 5$ in that order, and no more than $2$ consecutive cows may be chosen. Choosing every cow except the third gives a total efficiency of $1 + 2 + 4 + 5 = 12$, which is the maximum.