Ya vamos llegando a Péeeenjamoo ♫♫♫
В Пенхамо едут \(n\) семей, чтобы стать свидетелями крупнейшего в Мексике марафона по выгуливанию куриц на поводках. \(i\)-я семья состоит из \(a_i\) человек. Все семьи будут путешествовать на одном автобусе, состоящем из \(r\) рядов с \(2\) сиденьями в каждом.
Человек считается счастливым, если:
- Другой член семьи сидит в том же ряду, что и он; или
- Он сидит один в своем ряду (рядом с пустым местом).
Определите максимальное количество счастливых людей при оптимальной рассадке. Обратите внимание, что в автобусе должны сидеть все.
Гарантируется, что все члены всех семей могут поместиться в автобусе. Формально, гарантируется, что \(\displaystyle\sum_{i=1}^{n}a_i \le 2r\).
Выходные данные
Для каждого набора входных данных выведите максимальное количество счастливых людей при оптимальной рассадке.
Примечание
В первом наборе входных данных два члена первой семьи могут сидеть вместе в первом ряду, а два члена второй семьи могут сидеть вместе во втором ряду. Оставшийся член второй семьи может сидеть в третьем ряду вместе с членом третьей семьи. Такая рассадка показана ниже, и \(4\) счастливых человека окрашены в зеленый цвет.
| \(\color{green}{1}\) | \(\color{green}{1}\) |
| \(\color{green}{2}\) | \(\color{green}{2}\) |
| \(2\) | \(3\) |
Для второго набора входных данных ниже показан возможный вариант рассадки с \(6\) счастливыми людьми.
| \(\color{green}{3}\) | \(\color{green}{3}\) |
| \(\color{green}{1}\) | \(\color{green}{1}\) |
| \(\color{green}{2}\) | \(\color{green}{2}\) |
Для третьего набора входных данных ниже показана возможная рассадка с \(6\) счастливыми людьми.
| \(\color{green}{4}\) | \(\color{green}{4}\) |
| \(\color{green}{}\) | \(\color{green}{2}\) |
| \(\color{green}{3}\) | \(\color{green}{3}\) |
| \(\color{green}{1}\) | \(\color{green}{}\) |
| \(\color{green}{}\) | \(\color{green}{}\) |
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3
2 3 1
3 3
2 2 2
4 5
1 1 2 2
4 5
3 1 1 3
|
4
6
6
6
|