A - All to Almost Perfect ?

2 secs 1024 MB
matcharate12's icon matcharate12

Story

🍡

matcharate君は茶屋の見栄えをよくしようとするために、お店の外観を綺麗にしています。そのとき、副経営者であるtearate君は机の上にあるおぼんにいくつかのお団子を置きました。
確かにそれはいい案です。しかしtearate君が置いた感じだと、matcharate君は少し不満気そうです。なぜなら、それぞれのおぼんに乗せてるお団子の数がバラバラだからです。matcharate君は、これは大事な副経営者に喝を入れるチャンスだと思いました。

問題

テーブルの上に NN 個のおぼんがあります。そのうち左から i (1iN)i\ (1\le i\le N) 番目のおぼんでは AiA_i 個のお団子がありました。
tearate君は以下の操作を、各おぼんに対して 00 回以上繰り返し行います。

  • お団子を 11 つ作り、その作ったお団子をおぼん ii に新たに 11 つ置く

操作を繰り返し行い、各おぼんに対し乗ってるお団子の数がすべてちょうど LL または RR となるようにしたいです。
ですが、お団子の数が RR 個より多く乗っているおぼんには上の操作はしないようにします。

tearate君は少なくともいくつ以上のお団子を作る必要がありますか?

入力

入力は以下の形式で与えられる。

NNLLRR
A1A_1A2A_2\dotsANA_N

制約

  • 1N1031\le N\le 10^3
  • 2L<R1042\le L\lt R\le 10^4
  • 1Ai1041\le A_i\le 10^4
  • 入力はすべて整数

出力

答えを出力せよ。

入出力例

入力例1
4 4 5
1 2 3 6
出力例1
6

それぞれおぼん 1133 個、おぼん 2222 個、おぼん 3311 個だけお団子を作って乗せることにより、操作後のおぼんには 44 個ずつお団子が乗ってる状態になります。おぼん 44 には R(=5)R(=5) 個より多く乗っているので、操作を行いません。
合計で 3+2+1=63+2+1=6 個のお団子を作ることで条件を達成させることが可能です。55 個以下で達成する方法は存在しないので、66 を出力します。

入力例2
4 10 13
10 10 11 11
出力例2
4

おぼん 3,43,4 に対し 22 個ずつお団子を作って乗せることによって達成できます。あるおぼんに対し、操作を行わないことがあっても構いません。

入力例3
10 4 10
3 1 4 1 5 9 2 6 5 3
出力例3
25

Submit


Go (1.21)