A - All to Almost Perfect ?

2 secs 1024 MB
matcharate12

Story


🍡

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

問題


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

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

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

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

入力


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


制約


  • 入力はすべて整数

出力


答えを出力せよ。

入出力例


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

それぞれおぼん 個、おぼん 個、おぼん 個だけお団子を作って乗せることにより、操作後のおぼんには 個ずつお団子が乗ってる状態になります。おぼん には 個より多く乗っているので、操作を行いません。
合計で 個のお団子を作ることで条件を達成させることが可能です。 個以下で達成する方法は存在しないので、 を出力します。

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

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

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

提出


Go (1.14)