UOJ Logo Universal Online Judge

UOJ

#484. 【UR #18】绝对不鸽

统计

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

为了比拼咕咕咕能力,主持人交给了码农同学$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\} \rightarrow \{3, 4, 4\}\rightarrow \{3, 4, 0\}\rightarrow \{6, 6, 0\} \rightarrow \{6, 0, 0\} \rightarrow \{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 \% $ 的数据,$ 1 \le B \le n \le 10^5, 0 \le a_i, A \le 10^{12} $ 。 下表是更详细的数据范围,表中留空代表无特殊限制。

子任务编号$n$$A$$B$$a_i$分值
$1$$\le 10$$=1$$=1$$\le 1$$17$
$2$$\le 100$$\le 100$$\le 100$$16$
$3$$\le 2000$$=0$$11$
$4$$\le 2000$$27$
$5$$29$

时间限制: $ 2 $s

空间限制: $ 512 $MB

下载

样例数据下载