你有$n$个数字$a_1, a_2, \dots, a_n$。你要在里面选择若干个数字,满足任意一个长度为$k$的区间,比如$a_1, a_2, \dots, a_k$这些数里面,你不能选择超过一个。
问选出来的数字的和最大是多少。
提示:上面的条件相当于,如果你选了一个数$a_i$,那么上一个数必须$a_{i-k}$或者更加靠前的数字。
输入格式
第一行两个整数$n, k$。
接下来一行$n$个整数,$a_1, a_2, \dots, a_n$。
输出格式
一个整数,表示答案。
样例输入
5 2
100 1 1 100 1
样例输出
200
数据规模
对于所有数据,保证$1\leq k\leq n\leq 10^5, 1\leq a_i\leq 10^9$。