Летом все участники олимпиадных кружков «Летово» собираются в поход. Руководители похода заранее решили рассчитать количество палаток, которое необходимо взять с собой. Все палатки, которые есть на складе, трёхместные (вмещают не более \(3\) человек).
Всего среди участников кружков есть \(a\) интровертов, \(b\) экстравертов и \(c\) универсалов.
- Каждый интроверт хочет жить в палатке один. Таким образом, палатка с интровертом обязана содержать ровно одного человека — самого этого интроверта.
- Каждый экстраверт хочет жить в палатке с ещё двумя людьми. Таким образом, палатка с экстравертом обязана содержать ровно трёх человек.
- Каждого универсала устроит любой вариант: жить одному, вдвоём или втроём.
Скажите, какое минимальное количество палаток необходимо взять с собой, чтобы все участники смогли разместиться в соответствии со своими предпочтениями! Если же разместить участников так, чтобы выполнить все пожелания, невозможно, выведите \(-1\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество палаток или \(-1\), если разместить участников невозможно.
Примечание
В первом наборе входных данных \(1\) палатку нужно будет отдать интровертам, ещё в \(1\) палатке будут жить два экстраверта и один универсал, в последней будут жить два универсала. Итого \(3\) палатки.
Во втором наборе три экстраверта возьмут \(1\) палатку, также \(1\) палатку возьмет интроверт. Тогда останется один экстраверт и один универсал. Этот экстраверт никак не сможет поселиться с кем-то втроем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000
|
3
-1
3
-1
3
28
0
7
8
1666666667
|