Ribbons for the Festival


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

To decorate a school festival in Puerto Rico, you have a ribbon of length n. Cut it entirely into pieces, each of length exactly a, b or c. Each allowed length may be used any number of times, and you do not need to use all three.

Find the maximum number of pieces with no ribbon left over. At least one valid cutting is guaranteed to exist. The three allowed lengths may be equal.

Input

One line containing four integers: n, a, b and c.

Output

Print one integer: the maximum number of pieces.

Constraints

1 ≤ n, a, b, c ≤ 4 000.

Example
Input Example Output Example
9 2 3 5 4
7 5 5 2 2

Pieces of lengths 2, 2, 2 and 3 use the entire ribbon.

One piece of length 5 and one of length 2 use the entire ribbon.

Source

Adapted for OiPR 2026. Codeforces 189A — Cut Ribbon.


Comments

There are no comments at the moment.