ratb
Bucharest City Hall has decided to auction off one stand in each of the n stops on the route of bus 2006. For this purpose, City Hall conducted a feasibility study which estimated the monthly profits, in RON, that can be obtained by each stand. In some stops located in less trafficked areas, it was determined that it was possible to have no profit, but actually have losses (have negative profit!). In order to be able to sell all the stands anyway, City Hall decided that each interested investor should be obligated to buy all the stands located in at least k consecutive stations. Your task is to determine the sequence of stands for which an investor should bid in order for the estimated profit to be maximum. Because any investor would like to keep cordial relations with City Hall, should there be no sequence of stands which would bring a profit, it will still bid for a sequence of stands for which the loss is minimal.
Task
Determine the maximum profit that can be obtained on a sequence made up of at least k of the n stands, as well as the numbers of the first and the last stand in the sequence for which maximum profit is gained. The stands are numbered from 1 to n.
Input Data
Input file ratb.in contains on the first line the integers n and k, separated by a space, and on the second line n integers, separated by spaces, representing, in consecutive order, the estimated profits for the n stands.
Output Data
Output file ratb.out will contain on the first line the requested maximum profit and on the second line the numbers of the first and the last stand for which maximum profit is gained. If there is more than one sequence for which profit is maximal, the one closest to the beginning of the route will be considered (the starting stand number be minimal; if there is more than one solution with the minimal starting stand number, the solution that has the last stand number minimal will be selected).
Constraints
Examples
|
ratb.in |
ratb.out | ratb.in | ratb.out |
|
10 3 |
210 4 7 |
7 2 -35 -12 -60 49 -80 -100 -20 |
-11 3 4 |
| ratb.in | ratb.out |
| 10 3 -100 10 10 10 -70 10 10 10 -50 -20 |
30 |
Time limit: 0.1 seconds/test
lect. drd. Radu Boriga
"Titu Maiorescu" University - Bucharest
Contact:r_boriga@yahoo.com