Problem Description:
It is the
Annual Book Fair. There are thousands of book stalls and this year the
organizers introduced a new scheme. In every stall either you can collect a
coupon bearing a number but then you must skip next k stalls or you can simply
go to the next stall without collecting the coupon. At the end, your prize is
free books worth the sum of the numbers on the coupon you have collected.
Input Format:
The first
line has two positive integers, N (the number of stalls) and k (the number of
stalls to skip if you collect a coupon).
The next N
lines have 1 positive integer each, which is the value of the coupons you
collect from the corresponding stall.
Output
Format:
The output is
one number that is the maximum value of the sum of coupons collected according
to the rules.
Constraints:
N<50
Number on the
coupon <1000
Example 1
Input
10,2
4
5
8
7
5
4
3
4
6
5
Output
19
Explanation
N =10, k=2
The highest
value is obtained if you pick the stall numbers 1,4,7,10, giving a value of
4+7+3+5=19.
Example 2
Input
10,2
50
70
40
50
90
70
60
40
70
50
Output
230
Explanation
There are 10
stalls, and k=2. The coupon values are as shown. If you visit stalls 2, 5 and
9, you get a total value of 230, which is the maximum possible. The output is 230.
No comments:
Post a Comment