Giải bài trực tuyến

With brother’s help, DB has successed in flirt with TN. (see QTNOEL). But now he has another problem :

In Vietnamese Tet holidays (Vietnam’s Lunar New Year), there is a custom called ‘Li xi’ that adult give children money in red packs, to wish them strong and happy. DB’s family has a very special method to give children Li xi :

There are n Li xi packs, every pack has a[i] VND – Vietnamese unit of money, and a random positive integer k (1 ≤ k ≤ n). DB can take any pack, but mustn’t take k packs in a row.

Let’s help him to find the way to take the maximum of money.

Input :

-          First line : two integer n and k

-          Second line : n integer, the i-th number is a[i]

Output :

            A single number s – the maximum money DB can take.

Example:

Input:

5 3

6 19 8 7 13

Output:

45

Limit :

- 0 ≤ a[i] ≤ 2000

- n ≤ 10⁶