Ева — начинающий стендап комик. На ее первое выступление пришли целых два зрителя: Алиса и Боб.
Ева подготовила \(a_1 + a_2 + a_3 + a_4\) шуток, сгруппированных по типам:
- тип 1: Алисе и Бобу нравятся;
- тип 2: Алисе нравятся, а Бобу нет;
- тип 3: Бобу нравятся, а Алисе нет;
- тип 4: ни Алисе, ни Бобу не нравятся.
Изначально настроение обоих зрителей \(0\). Когда зритель слышит шутку, которая ему нравится, его настроение увеличивается на \(1\). Когда зритель слышит шутку, которая ему не нравится, его настроение уменьшается на \(1\). Если настроение становится отрицательным (строго меньше нуля), то зритель уходит.
Когда кто-то уходит, Еве становится грустно, и она заканчивает выступление. Если никто не уходит, а у Евы заканчиваются шутки, то она тоже заканчивает выступление.
Поэтому Ева бы хотела рассказать шутки в таком порядке, чтобы выступление длилось как можно дольше. Помогите ей посчитать наибольшее количество шуток, которые она может рассказать до того как выступление закончится.
Выходные данные
На каждый набор выходных данных выведите одно целое число — наибольшее количество шуток, которые Ева может рассказать до того как хотя бы один из зрителей уйдет или как у нее закончатся шутки.
Примечание
В первом наборе входных данных Ева подготовила только шутки первого типа. Поэтому тут не выберешь порядок. Она рассказывает все свои штуки, и Алисе, и Бобу они нравятся. Их настроение становится \(5\). Выступление заканчивается после того как у Евы заканчиваются шутки.
Во втором наборе входных данных Ева подготовила только шутки четвертого типа. Опять же не выберешь порядок. Она рассказывает шутку, и ни Алисе, ни Бобу она не нравится. Их настроение уменьшается на один, становится \(-1\). У них обоих отрицательное настроение, поэтому они оба уходят, и выступление заканчивается.
В третьем наборе входных данных Ева сначала рассказывает обе шутки первого типа. У Алисы и Боба становится настроение \(2\). Затем \(2\) шутки третьего типа. Настроение Алисы \(0\). Настроение Боба \(4\). Затем \(4\) шутки второго типа. Настроение Алисы \(4\). Настроение Боба \(0\). Затем еще \(4\) шутки третьего типа. Настроение Алисы \(0\). Настроение Боба \(4\). Затем оставшуюся шутку второго типа. Настроение Алисы \(1\). Настроение Боба \(3\). Затем еще шутку третьего типа и четвертого типа, например. Настроение Алисы становится \(-1\), и она уходит.
В четвертом наборе входных данных Ева должна сначала рассказать шутки, которые нравятся обоим зрителям, затем шутки, которые не нравятся никому. Она может рассказать \(4\) шутки четвертого типа, пока зрители не уйдут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5 0 0 0
0 0 0 5
2 5 10 6
3 0 0 7
|
5
1
15
7
|