An Amazon ads team is analyzing
The profit from time slot
The team wants to run exactly
Each campaign must cover a non-empty contiguous segment of time slots.
No two campaigns may overlap.
Each campaign can have length at most
Your task is to find the maximum total profit possible by choosing exactly
The first line contains three integers KaTeX can only parse string typed expression, KaTeX can only parse string typed expression, and KaTeX can only parse string typed expression — the number of time slots, the number of campaigns, and the maximum allowed length of one campaign.
The second line contains KaTeX can only parse string typed expression integers KaTeX can only parse string typed expression — the profit of each time slot.
Print a single integer — the maximum total profit possible by choosing exactly KaTeX can only parse string typed expression non-overlapping campaigns.
Input
6 2 2
5 -10 4 3 -2 613Choose the campaign covering time slots KaTeX can only parse string typed expression to KaTeX can only parse string typed expression, with profit KaTeX can only parse string typed expression.
Choose the campaign covering time slot KaTeX can only parse string typed expression, with profit KaTeX can only parse string typed expression.
The total profit is KaTeX can only parse string typed expression.
Example 2:
Input
3 3 1
-5 -2 -7-14Each campaign must have length exactly KaTeX can only parse string typed expression because KaTeX can only parse string typed expression, and exactly KaTeX can only parse string typed expression campaigns are required. The total profit is KaTeX can only parse string typed expression.
Example 3:
Input
5 1 3
1 2 3 4 512Only one campaign is needed. The best valid campaign has length at most KaTeX can only parse string typed expression and covers time slots KaTeX can only parse string typed expression to KaTeX can only parse string typed expression, with profit KaTeX can only parse string typed expression.