Middle Earth Technical University organizes a coding competition. In this competition, people play with each other using AI programs that they write. Every pair of programmers play with each other, and winner steals \(K\) points from the loser's rating and adds it to their rating. If the loser has less than \(K\) rating, the winner steals all of their ratings.

Can you find the maximum rating after a total of \(M\) matches?

Note that all of the \(M\) matches can be done by the same competitor.

Input

First-line contains the integers \(N\) (the number of contestants), \(K\) (the number of points that the winner steals from the loser), and \(M\) (the number of total matches).

The second line contains an array of \(N\) nonnegative integers. \(A_i\) correspond to \(i^{th}\) contestant's rating.

• \(1 \leq \mathbf{N, K} \leq 10^{5}\)
• \(1 \leq \mathbf{A_i} \leq 10^{5}\)

Output

Print the maximum rating after \(M\) matches.

Examples

Input:

4 2 3
1 2 3 4

Output:

9

Input:

4 1 4
1 1 1 4

Output:

7