Однажды, рано утром, вы решили сходить в магазин неподалеку и купить там пачку чипсов. В магазине продаются чипсы \(n\) разных вкусов. Пачка чипсов с \(i\)-м вкусом стоит \(a_i\) бурлей.
В магазине могут закончиться чипсы каких-то вкусов, а потому вы решили выбрать пачку уже после того как придете в магазин. Однако у данного плана есть две серьезные проблемы:
- у вас есть только монеты номиналом \(1\), \(2\) и \(3\) бурля;
- так как еще утро, в магазине вас попросят заплатить без сдачи, т. е. если вы выберете пачку чипсов с \(i\)-м вкусом, вы должны будете заплатить ровно \(a_i\) бурлей.
Носить много монет тяжело, а потому вам хочется взять наименьшее суммарное количество монет. Соответственно, вас интересует вопрос: какое наименьшее количество монет вам нужно будет взять с собой, чтобы вы могли расплатиться за пачку чипсов любого вкуса без сдачи?
Выходные данные
Для каждого набора входных данных выведите одно число — наименьшее количество монет, которое вам понадобится взять с собой, чтобы купить пачку чипсов любого вкуса без сдачи.
Примечание
В первом наборе входных данных, вы можете, например, взять с собой \(445\) монеты с номиналом \(3\) и \(1\) монету номинала \(2\). Таким образом, вы наберете \(1337 = 445 \cdot 3 + 1 \cdot 2\).
Во втором наборе, вы можете, например, взять \(2\) монеты номинала \(3\) и \(2\) монеты номинала \(2\). Так вы сможете заплатить как ровно \(8 = 2 \cdot 3 + 1 \cdot 2\), так и ровно \(10 = 2 \cdot 3 + 2 \cdot 2\).
В третьем наборе, достаточно взять \(1\) монету номинала \(3\) и \(2\) монеты номинала \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
1337
3
10 8 10
5
1 2 3 4 5
3
7 77 777
|
446
4
3
260
|