Cut Ribbon
题目描述
Polycarpus has a ribbon, its length is n. He wants to cut the ribbon in a way that fulfils the following two conditions:
- After the cutting each ribbon piece should have length a, b or c.
- After the cutting the number of ribbon pieces should be maximum.
Help Polycarpus and find the number of ribbon pieces after the required cutting.
The first line contains four space-separated integers n, a, b and c (1≤n,a,b,c≤4000) − the length of the original ribbon and the acceptable lengths of the ribbon pieces after the cutting, correspondingly. The numbers a, b and c can coincide.
Print a single number − the maximum possible number of ribbon pieces. It is guaranteed that at least one correct ribbon cutting exists.
5 5 3 2
2
7 5 5 2
2
In the first example Polycarpus can cut the ribbon in such way: the first piece has length 2, the second piece has length 3.
In the second example Polycarpus can cut the ribbon in such way: the first piece has length 5, the second piece has length 2.
题目来源：fps-www.educg.net-codeforce-1-2833.xml.zip；FPS 共享题包，题包内第 2492 题。保留原作者与原赛事署名。