你有一本包含 $n$ 个法术的法术书。法术按 $1$ 到 $n$ 的整数编号，法术 $i$ ($1 \le i \le n$) 的初始消耗为 $A_i$ 点 MP（法力值）。你初始拥有 $m$ 点 MP。

你的目标是将法术书中的每个法术各施放恰好一次。

在开始施放法术之前，你可以吃掉最多 $k$ 个饼干。吃饼干不消耗时间。每吃一个饼干，你可以选择一个消耗为正的法术，并将其消耗减少 $1$。

吃完饼干后，你开始施放法术。

你可以重复选择并执行以下操作之一： 选择一个整数 $i$ ($1 \le i \le n$) 并施放法术 $i$。前提是当前的 MP 必须大于或等于 $A_i$。此操作不消耗时间，并使你的 MP 减少 $A_i$。 如果你的 MP 为 $z < m$，你可以休息以恢复 $1$ 点 MP。这需要 $m - z$ 秒（例如，如果 $m = 5$ 且 $z = 2$，你需要休息 $3$ 秒将 MP 从 $2$ 恢复到 $3$）。

求出将 $n$ 个法术各施放恰好一次所需的最少时间。你可以自由选择施放法术的顺序。

输入格式

第一行包含三个整数 $n$、$m$ 和 $k$：分别为法术数量、初始 MP 值和饼干数量。 第二行包含 $n$ 个整数 $A_i$：法术的初始 MP 消耗 ($1 \le n \le 10^5$, $1 \le m \le 10^6$, $1 \le A_i \le m$, $0 \le k \le \sum_{i=1}^n A_i$)。

输出格式

输出一个整数：将 $n$ 个法术各施放恰好一次所需的最少时间。

样例

样例输入 1

2 4 0
2 4

样例输出 1

3

样例输入 2

3 9 6
2 3 9

样例输出 2

0

样例输入 3

3 16 2
6 9 9

样例输出 3

21

样例输入 4

2 1000000 0
1000000 1000000

样例输出 4

500000500000