1158. Maximum Ribbon Cut

Given a ribbon of length n and a set of allowed piece sizes, cut the ribbon into the maximum number of pieces where every piece length is in the set. Return that maximum count, or -1 if the ribbon cannot be cut exactly. The input is JSON {n, sizes}.

Input: JSON {n, sizes}.

Output: Integer — the maximum number of pieces, or -1.

Examples

Input: {"n":5,"sizes":[2,3,5]}
Output: 2
Explanation: Cut into 2 and 3.

Input: {"n":5,"sizes":[4,6]}
Output: -1
Explanation: Cannot cut exactly.

Input: {"n":7,"sizes":[2,5]}
Output: 2
Explanation: Cut into 2 and 5.

Constraints

• 1<=n<=1000
• 1<=sizes<=100

Asked by