После вкусного обеда в столовой ученикам приходится стоять в очереди, чтобы сдать посуду. Стоять в очереди никто не хочет, потому что тратится время бесполезно. Динислам смекнул, что можно встать не в самый конец очереди, а на много дальше от конца. Идея такая: он подходит к ученику стоящему дальше от конца, и забирает его посуду, сам при этом встает на его место. Ученику, который отдал посуду, стоять в очереди не нужно, а Динислам не в самом конце. В итоге посуду сдает только один человек. Все в плюсе!
В начальный момент времени в очереди стоят $$$n$$$ человек. Дальше приходит Динислам, который заражает своей супер идеей подходящих после него (ему самому, естественно, своя идея тоже нравится :-). Однако не все готовы воспользоваться этой супер идеей. У каждого ученика есть свой предел: он равен либо 1, либо 2, это означает сколько посуды ученик может нести с собой.
За 1 секунду времени 1 ученик может сдать всю посуду, которая у него имеется.
Замена одного ученика на другого происходит моментально, времени не занимает.
Динислам хочет узнать за какое минимальное время ученики сдадут всю свою посуду. В начальный момент времени считать, что очередь с Динисламом уже образовалась.
На первой строке даны $$$n$$$ и $$$k$$$ ($$$1 \le k, n \le 10^5$$$) – количество учеников в очереди в начальный момент времени и количество учеников, идущих к очереди вместе с Динисламом.
В следующей строке даны $$$k$$$ чисел ($$$a_1, a_2, ..., a_k$$$) – пределы учеников, т.е. количество посуды, которую они готовы нести. Каждое из чисел может быть либо $$$1$$$ либо $$$2$$$. Если $$$a_i = 1$$$, то ученик не собирается уходить со своего места, брать чужую посуду и вставать на другое место, иначе ученик может встать в основную очередь вместо другого ученика, либо захочет забрать посуду впереди стоящего, так как в этом случае время также экономится.
Минимальное время, за которое все ученики сдадут посуду.
| Группы | Баллы | Ограничения |
| $$$1$$$ | $$$25$$$ | $$$a_i = 1$$$ |
| $$$2$$$ | $$$25$$$ | $$$a_i = 2$$$ |
| $$$3$$$ | $$$50$$$ | нет ограничений |
6 4 1 2 1 2
8
3 6 2 2 2 2 2 2
5
2 5 1 1 1 1 1
7
В первом примере 2 и 4 ученики могут взять посуду, как у стоящих в первой очереди, так и во второй очереди и встать на их место.
Во втором примере 3 первых ученика из второй очереди перемещаются в первую, сдают посуду за 3 секунды, далее 5-й берет посуду у четвертого и сдает, и остается 6-му сдать свою. Получаем 5 секунд.
В третьем примере никто никуда перемещаться не хочет, поэтому ответ 7 секунд.
В начальный момент времени 
После того как ученики из второй очереди перегруппировались $$$ \\ $$$ (синего цвета человечки – это ученики, взявшие посуду и вставшие на другое место)
