题目描述

0xC0000005有n个妹子，每个妹子都有一个美丽值Ai，现在0xC0000005想选出连续的不超过m个妹子，使得这些妹子的美丽值最大

输入格式

第一行有两个由空格分隔的正整数n，m.

第二行有n个数，表示A1,A2,...,An 每两个数之间由一个空格分隔.

输出格式

一个数，为最大子段和。

输入样例

5 2
1 -2 9 -3 5

输出样例

9

数据规模与约定

对于30%的数据，有n,m≤1,000

对于60%的数据，有n,m≤10,000

对于100%的数据，有n,m≤100,000，−231<Ai<231.