1426: 热气球
Memory Limit:256 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:107
Solved:43
Description
[md]
旅游景区新开设了一项极其刺激的游乐项目——热气球飞行。
在确定票价之前,景区想先对游客的乘坐意愿和消费能力进行一次摸底。
有n个游客按顺序排成一队,每人都填报了一个数字,表示他(她)愿意花多少钱去体验这个项目。
因为项目对游客的勇气有极高要求,有些人填报的数字可能是负数,表示只有当有人给他(她)钱的情况下才愿意去乘坐。
热气球最多乘坐m个人,景区的组织者想从这n个游客中选出连续的不超过m个,乘坐热气球飞行,使得这趟飞行获得的收益最大(收益用钱数衡量,即这不超过m个游客,填报的数字之和)。
请你计算组织者可能获得的最大收益。 [/md]
在确定票价之前,景区想先对游客的乘坐意愿和消费能力进行一次摸底。
有n个游客按顺序排成一队,每人都填报了一个数字,表示他(她)愿意花多少钱去体验这个项目。
因为项目对游客的勇气有极高要求,有些人填报的数字可能是负数,表示只有当有人给他(她)钱的情况下才愿意去乘坐。
热气球最多乘坐m个人,景区的组织者想从这n个游客中选出连续的不超过m个,乘坐热气球飞行,使得这趟飞行获得的收益最大(收益用钱数衡量,即这不超过m个游客,填报的数字之和)。
请你计算组织者可能获得的最大收益。 [/md]
Input
第一行一个整数n;
第二行一个整数m(1<=m<=n<100);
第三行,以字符串形式输入n个不相同的整数(大小在-100~100范围内),相邻两个整数用一个空格分隔,依次表示每个游客愿意花多少钱去体验这个项目。
Output
一个整数,代表景区的组织者可能获得的最大收益。
Sample Input Copy
5
2
1 2 3 2 1
Sample Output Copy
5