题目描述

有 $N$ 个数，需要划分为若干个连续小组，每组至少一个、至多 $M$ 个数。一个小组中的所有数都可以变为该组的最大值。请合理划分，使变换后所有数的总和最大，并输出这个最大值。

输入格式

第一行包含两个整数 $N,M$。 接下来 $N$ 行每行包含一个正整数 $P_i$，表示第 $i$ 个数。

输出格式

输出一个整数，表示变换后总和的最大值。

样例

7 3
1
15
7
9
2
5
10

84

数据范围与提示

• $1 \le N \le 10^4$
• $1 \le M \le 10^3$
• $1 \le P_i \le 10^5$