После окончания уроков n групп школьников вышли на улицу и собрались ехать домой к Поликарпу на празднование его дня рождения. Известно, что i-ая группа состоит из si друзей (1 ≤ si ≤ 4), которые не хотят расставаться по пути к Поликарпу. Решено ехать на такси. Каждая машина может вместить не более четырех пассажиров. Какое минимальное количество машин потребуется школьникам, если каждая группа должна целиком находиться в одной из машин такси (но одна машина может вмещать более чем одну группу)?
Выходные данные
Выведите единственное число — минимальное необходимое количество такси, чтобы отвезти всех ребят к Поликарпу.
Примечание
В первом тесте возможно следующее распределение по четырем машинам:
- третья группа (из четырех школьников),
- четвертая группа (из трех школьников),
- пятая группа (из трех школьников),
- первая и вторая группы (из одного и двух школьников соответственно).
Существуют и другие способы расположиться в четырех машинах.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 4 3 3
|
4
|
|
2
|
8
2 3 4 4 2 1 3 1
|
5
|