Zayin is a wizard fighting monsters. This time, he faces $n$ monsters standing in a row, where the $i$-th monster has $a_i$ health points.

However, for some mysterious reason, Zayin cannot control which monster he hits. Specifically, there exists a permutation $p$ of length $n$ such that whenever Zayin attempts to attack the $i$-th monster, he is actually attacking the $p_i$-th monster.

Each time, Zayin can choose an integer $k \in [1, n]$ to reduce the health of the $p_k$-th monster by 1 point. A monster dies when its health is less than or equal to 0.

Zayin does not know what the permutation $p$ is, nor can he see the remaining health of each monster; he only knows whether a monster dies after each attack.

Now, Zayin wants to know the maximum number of attacks required to kill $m$ monsters, assuming he follows an optimal strategy.

Input

The first line contains two positive integers $n, m$ ($1 \le m \le n \le 2000$), where $n$ is the number of monsters and $m$ is the number of monsters Zayin needs to kill.

The second line contains $n$ non-negative integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ represents the health of the $i$-th monster.

Output

Output a single integer, the minimum number of attacks required in the worst case.

Examples

Input 1

2 1
10 15

Output 1

15

Input 2

2 1
10 30

Output 2

20

Note

In the first example, Zayin will keep attacking a certain monster until it dies.

In the second example, Zayin first attacks a certain monster 10 times. If it does not die, it means he is attacking the monster with 30 health. At this point, Zayin will choose to attack the second monster. After 10 more attacks, the other monster will definitely die, so in the worst case, 20 attacks are required.

Constraints

• For 10% of the data, $1 \le n, m \le 5$.
• For another 20% of the data, all $a_i$ are equal.
• For another 30% of the data, $1 \le m \le n \le 500$.
• For 100% of the data, $1 \le m \le n \le 2000$, $1 \le a_i \le 10^9$.