Character Training
Time limit2sMemory limit128 MB
Given character counts and power values per level, decide how to spend at most D training days across characters to maximize total power.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Greedy, Array
- Solved
- No attempts yet
Problem
Haebin has several characters. Each character's level is an integer from 1 through N. During the next D days, Haebin wants to train characters so that the total power of all characters becomes as large as possible.
On each day, Haebin may choose one character to train. If the chosen character's level is below N, training it for one day increases its level by 1. A character already at level N does not gain a level from training. The same character may be trained on consecutive days, and Haebin may also rest on any day without training a character.
For each level, you are given how many characters currently have that level. You are also given the power of a character at each level. Compute the maximum possible total power after at most D days of training.
Consider this situation: the maximum level is 5, the numbers of characters at levels 1, 2, 3, 4, and 5 are 1, 2, 3, 4, and 5, and the powers of those levels are 1, 2, 3, 4, and 5. The initial total power is 11 + 22 + 33 + 44 + 5*5 = 55. With 10 days of suitable training, the total power can become 65.
Input
The first line contains the maximum character level N (1 <= N <= 50). The second line contains the number of Haebin's characters at each level, from level 1 to level N. The third line contains the power of a character at each level, from level 1 to level N. Each count and each power is a nonnegative integer at most 1,000,000. The fourth line contains the number of available training days D (1 <= D <= 100).
Output
Print the maximum possible total power of all characters after training for at most D days.
Hint
In the second visible test, four level-4 characters can be trained to level 5 in 4 days, and three level-3 characters can be trained to level 5 in 6 days.