题目描述

easy版与hard版的唯一区别在于 $n$ 和 $m$ 的范围。 在上一次的比赛中，我们知道了美丽值这种东西。很不幸，在最新的研究中，珂学家发现之前美丽值的计算是错误的。 事实上，美丽值的定义是在一个长度为 $n$ 的序列中，找到一段长度不超过 $m$ 的连续子序列，使得子序列中所有数的和最大。子序列的长度至少是 $1$。

注意：对于 $[1,2,3,4,5]$ 这组序列, $[1,2,3]$ 为连续子序列, $[1,2,4]$ 不为连续子序列

输入格式

第一行输入两个整数 $n$, $m$。

第二行输入 $n$ 个数，代表长度为 $n$ 的整数序列。 $1 \\leq n,m \\leq 2000$ $-10^9 \\leq a_i \\leq 10^9$

输出格式

输出一个整数，代表该序列的最大的美丽值。

样例

6 4 
1 -3 5 1 -2 3

7

提示

by 励翔 2022春第三次排位赛