Problem1176--「一本通 5.5 例 2」最大连续和

1176: 「一本通 5.5 例 2」最大连续和

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

给你一个长度为 nnn 的整数序列 {A1,A2,⋯ ,An}\{A_1,A_2,\cdots ,A_n\}{A1,A2,,An},要求从中找出一段连续的长度不超过 mmm 的子序列,使得这个序列的和最大。


Input

第一行为两个整数 n,mn,mn,m

第二行为 nnn 个用空格分开的整数序列,每个数的绝对值都小于 100010001000


Output

仅一个整数,表示连续长度不超过 mmm 的最大子序列和。


Sample Input

6 4
1 -3 5 1 -2 3

Sample Output

7

HINT

对于 50%50\%50% 的数据,1≤N,M≤1041\le N,M\le 10^41N,M104

对于 100%100\%100% 的数据,1≤N,M≤2×1051\le N,M\le 2\times 10^51N,M2×105


Source/Category


Submit Status