K個のケーキ

```cpp 某人有K块蛋糕，他想每天吃一块，正好K天吃完。 这K块蛋糕共分为T种，第i种蛋糕有a[i]个。 这个人不想连续两天吃同样种类的蛋糕，他想知道自己最少有多少天自己吃的蛋糕和前一天吃的蛋糕种类一样。 ```

[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 $

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

7 3
3 2 2

0

6 3
1 4 1

1

100 1
100

99

### 制約 - $ 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日目以降は毎日前日と同じ種類のケーキを食べるしかありません。