1157. Minimum Cost to Fill Given Weight

You may buy packets of various weights, where cost[i] is the price of a packet weighing i+1 units (a value of -1 means that weight is unavailable). With unlimited supply of available packets, return the minimum cost to buy exactly W units of weight, or -1 if impossible. The input is JSON {cost, W}.

Input: JSON {cost, W}.

Output: Integer — the minimum cost, or -1.

Examples

Input: {"cost":[20,10,4,50,100],"W":5}
Output: 14
Explanation: 2 units (10) + 3 units (4).

Input: {"cost":[-1,-1,4,5,-1],"W":5}
Output: -1
Explanation: Cannot form exactly 5.

Input: {"cost":[1],"W":1}
Output: 1
Explanation: One unit packet.

Constraints

• 1<=n<=100
• 1<=W<=n

Asked by