AT_codefestival_2016_qualC_b K個のケーキ

[problemUrl]: https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_b $ K $ 個のケーキがあります。高橋君は、1日に一つずつ、$ K $ 日かけてこれらのケーキを食べようと考えています。 ケーキは$ T $ 種類あり、種類$ i\ (1≦i≦T) $ のケーキは$ a_i $ 個あります。 二日連続で同じ種類のケーキを食べると飽きてしまうため、高橋君は、うまくケーキを食べる順番を決めて、前日と同じ種類のケーキを食べる日数を最小にしようと考えました。 高橋君のために前日と同じ種類のケーキを食べる日数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ T $ $ a_1 $ $ a_2 $ $ ... $ $ a_T $

前日と同じ種類のケーキを食べる日数の最小値を出力せよ。

### 制約 - $ 1≦K≦10000,\ 1≦T≦100 $ - $ 1≦a_i≦100 $ - $ a_1+a_2+ $...$ +a_T\ =\ K $ ### Sample Explanation 1 ケーキは$ 7 $個あります。例えば種類$ 2,1,2,3,1,3,1 $の順で食べると一度も前日と同じ種類のケーキを食べなくてすみます。 ### Sample Explanation 2 ケーキは$ 6 $個あります。種類$ 2,3,2,2,1,2 $の順で食べると4日目だけ前日と同じ種類$ 2 $のケーキを食べることになり、これが最小になるので答えは$ 1 $です。 ### Sample Explanation 3 高橋君は一種類のケーキしか持っていないため、2日目以降は毎日前日と同じ種類のケーキを食べるしかありません。