1492: 吃东西 Hard version
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：114
Solved：17
Description
天禄面前有 $n$ 个宝物，每个宝物有好有坏，其中 $a_i$ 表示第 $i$ 个宝物的价值，由于无法看出宝物的好坏，天禄将按顺序吃掉这些宝物，初始营养值为 $0$ , 每吃掉一个宝物，天禄就会获得该宝物的价值，一旦当前营养值低于$0$，天禄则会吐出肚中所有的宝物，继续吃还没吃过的宝物。
天禄的哥哥辟邪为了让弟弟获得更多营养，他有 $k$ 次提醒机会，当辟邪在轮到第 $i$ 个宝物时提醒，天禄则会跳过这个宝物(将其视为吃过)。
问天禄最终获得的营养值最大为多少？
天禄的哥哥辟邪为了让弟弟获得更多营养，他有 $k$ 次提醒机会，当辟邪在轮到第 $i$ 个宝物时提醒，天禄则会跳过这个宝物(将其视为吃过)。
问天禄最终获得的营养值最大为多少？
Input
第一行包含两个整数 $n$ 和 $k$ ( $1 \leq n, k\leq 10^3$ ) --宝物的数量以及辟邪可以提醒的次数。
第$2$行包含 $n$个整数 $a_1, a_2, ..., a_n$( $-10^3 \leq a_i \leq 10^3$) - 第 $i$ 个宝物的营养值。
第$2$行包含 $n$个整数 $a_1, a_2, ..., a_n$( $-10^3 \leq a_i \leq 10^3$) - 第 $i$ 个宝物的营养值。
Output
输出一个整数，天禄最终获得的最大营养值。
Sample Input Copy
7 2
100 -200 -300 1 1 10 -5Sample Output Copy
107