Spenser has a big announcement. Are you ready?
Spenser's big announcement is words long and will be published on a banner. The message will be written out over a banner that is
meters tall
and
nanometers wide. The message will be broken up into
lines, and
the words in the message must be written in the order that Spenser's announcement has them in.
For each word, we know how many nanometers of width it takes up on the banner.
For readability purposes, two words that are adjacent on the same line line must be separated by exactly nanometers.
The banner must also have at least one word on every line.
Determine the optimal way to break up the message over the lines such that
the width of the resulting banner is minimized.
Constraints
Subtask 1 [1 point]
Subtask 2 [1 point]
No additional constraints.
Input Specification
The first line contains three integers, ,
, and
.
The next line contains integers, the widths of the words in nanometers
in order. Specifically, the
integer in the line,
, is the width of word
.
Sample Input 1
4 2 1
1 2 3 8
Sample Output 2
8
Sample Explanation 1
In this example, it is optimal to assign the first three words to the first line and the last word to the second line. The first three words will take up a total of 8 nanometers - 6 due to the width and 2 for the necessary gaps, and the last line will take up exactly 8 nanometers.
How Ampliteers will read the banner is an exercise left to Spenser.
Sample Input 2
12 1 100000000
100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000 100000000
Sample Output 2
2300000000
Sample Explanation 2
Since there is only one line, there is only one way to format the banner.
Comments