У Поликарпа есть ленточка длины n. Он хочет разрезать ее так, чтобы выполнялись два условия:
- После разрезания, каждый кусочек ленточки должен быть длины a, b или c.
- Количество кусочков ленточки после разрезания должно быть как можно больше.
Помогите Поликарпу, найдите количество кусочков ленточки после требуемого разрезания.
Выходные данные
Выведите одно число — максимально возможное количество кусочков ленточки. Гарантируется, что существует хотя бы одно корректное разрезание ленточки.
Примечание
В первом тестовом примере нужно разрезать ленточку на два кусочка: один из них длины 2, второй длины 3.
Во втором примере нужно разрезать ленточку на два кусочка: один из них длины 5, второй длины 2.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 3 2
|
2
|
|
2
|
7 5 5 2
|
2
|