Ribbons for the Festival
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