## 20B Rating

View as PDF

Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

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