Spenser has a big announcement. Are you ready?

Spenser's big announcement is ~n~ words long and will be published on a banner. The message will be written out over a banner that is ~l~ meters tall and ~w~ nanometers wide. The message will be broken up into ~l~ 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 ~s~ nanometers. The banner must also have at least one word on every line.

Determine the optimal way to break up the message over the ~l~ lines such that the width of the resulting banner is minimized.

Constraints

~1 \le l \le n \le 10^5~

~1 \le s, w_i \le 10^8~

Subtask 1 [1 point]

~l \le 2~

Subtask 2 [1 point]

No additional constraints.

Input Specification

The first line contains three integers, ~n~, ~l~, and ~s~.

The next line contains ~n~ integers, the widths of the words in nanometers in order. Specifically, the ~i^\texttt{th}~ integer in the line, ~w_i~, is the width of word ~i~.

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.