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.
示例1
输入
5 5 3 2<br />7 5 5 2<br />
备注:
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.
加载中...