Type: Default 1000ms 256MiB

总之就是非常开心

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

总之就是非常开心

题目描述

由崎星空和由崎司打算去旅游,但是由崎星空突然接到了一个工作,有n个任务需要他完成,这是一项巨大的工程,所以完成第ii个任务时,他就会增加aia_i点疲劳值,当他完成所有任务之后,他可以选择下面两种的其中一个:

  1. 独自休息会让他每秒减少1点的疲劳值。
  2. 和由崎司出去玩,他就会花费2*t秒的时间,同时减少q点疲劳值。

由于只有当由崎星空疲劳值恰好为0时,他才会出发去旅游,所以请告诉他们最少需要多少秒才能出发去旅游。

输入

第一行输入三个整数n,t,q,含义如题所示。(1<=n<=1051<=t<=q<=10181<=n<=10^5,1<=t<=q<=10^{18})

第二行输入n个整数,a1a_1a2a_2.....ana_n,(0<=aia_i<=101310^{13})。

输出

输出仅一行,如题所示

样例

样例1

4 1 3
2 4 5 7
12

样例2

4 1 2
1 1 1 1
4