Marica

Time limit1sMemory limit512 MB

Summary

Pick target counts for baskets so every value in [A,B] appears, minimizing total plum additions and removals.

Level: Medium6 of 10
Topics: Greedy, Sorting, Implementation
Solved: No attempts yet

Problem

Marica's grandmother keeps a large orchard and carries plums to the market every morning. This morning Marica filled $n$ baskets with plums for her, but grandmother stayed out late last night and is still asleep, so Marica wants to fool around a little longer. She will eat some of the plums from the baskets and pick more plums in the orchard.

Marica wants every natural number $k$ in the interval $[A, B]$ to be the exact number of plums in at least one basket. Both endpoints $A$ and $B$ belong to the interval. Given how many plums each basket holds right now, find the smallest number of operations Marica needs to reach her goal. One operation is one of the following.

Eat one plum from some basket.
Pick one plum in the orchard and put it into some basket.

Input

The first line contains the number of baskets $n$ . ( $1 \le n \le 5000$ )

The second line contains two natural numbers $A$ and $B$ . ( $1 \le A \le B \le 10^6$ , $B - A + 1 \le n$ )

The $i$ -th of the next $n$ lines contains $a_i$ , the number of plums in basket $i$ . ( $1 \le a_i \le 10^6$ )

Output

Print the smallest number of operations on the first line.

Examples2

Example 1
Input
```
5
3 6
8
7
1
10
9
```
Expected output
```
11
```
Example 2
Input
```
7
64 68
62
5
97
66
74
47
86
```
Expected output
```
45
```