1156. Maximize the Cut Segments

Given a rod of length n and three allowed cut lengths x, y, and z, cut the rod into the maximum number of pieces where every piece has length x, y, or z. Return that maximum count, or 0 if the rod cannot be exactly cut. The input is JSON {n, x, y, z}.

Input: JSON {n, x, y, z}.

Output: Integer — the maximum number of segments.

Examples

Input: {"n":5,"x":5,"y":3,"z":2}
Output: 2
Explanation: Cut into 3 and 2.

Input: {"n":4,"x":2,"y":1,"z":1}
Output: 4
Explanation: Four pieces of length 1.

Input: {"n":3,"x":2,"y":2,"z":2}
Output: 0
Explanation: Cannot cut exactly.

Constraints

• 1<=n<=10^4
• 1<=x,y,z<=10^4

Asked by