成为鸽王的三个要求之一，出色的咕咕咕能力。

为了比拼咕咕咕能力，主持人交给了码农同学$n$个待办事项，最初第$i$个待办事项还剩下$a_i$天的待办时间。

接下来码农同学和主持人会进行$9^{9^9}$轮交互，每一轮交互如下：

首先，码农同学可以找到不超过$A$个借口，并将这些借口任意分配给各个待办事项，每个借口都可以使某一个的待办事项增加$1$天的待办时间。

然后，主持人会选择$B$个待办事项，要求码农同学立即完成这些待办事项，将这些待办事项的待办时间清零。当然，这些待办事项的待办时间依然可以在后续轮次的交互中被增加。

在$9^{9^9}$轮交互全部完成之后，码农同学发现在整个交互过程中，在他某一次找借口后，某一个待办事项的待办时间达到了历史最大值$M$天，他可以借这个数值$M$来吹嘘自己的咕咕咕能力。

码农同学自然希望数值$M$尽量大，而主持人的目的则是让数值$M$尽量小。

观看大赛的观众们想要请你预测，假如码农同学和主持人一直使用最优策略，最终的数值$M$会是多少。

输入格式

输入的第一行包括三个整数 $n,A,B$ 。

接下来一行包括 $n$ 个非负整数，表示序列 $a$ ，即每个待办事项的初始待办天数。

输出格式

输出共包括一行，表示答案。

样例一

input

3 5 1
1 2 3

output

11

explanation

一种交互过程如下：

$\{1,2,3\}\to \{3,4,4\}\to \{3,4,0\}\to \{6,6,0\}\to \{6,0,0\}\to \{11,0,0\}$

样例二

input

5 5 1
0 2 1 0 3

output

14

样例三

input

5 100 5
1 2 3 4 5

output

105

样例四

input

19 23333 7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output

30471

样例五

input

10 1 1
100 90 80 70 60 50 40 30 20 10

output

101

样例六

input

8 3 1
5 1 2 2 0 2 5 1

output

9

限制与约定

对于 $100\mathrm{\%}$ 的数据，$1\le B\le n\le {10}^5,0\le a_i,A\le {10}^{12}$ 。 下表是更详细的数据范围，表中留空代表无特殊限制。

时间限制: $2$s

空间限制: $512$MB

下载

样例数据下载