815. Minimum Cost to Fill Given Weight in Bag

Given an array costs where costs[i] is the cost of a packet weighing (i+1) kg (or -1 if unavailable), and a target weight W, return the minimum cost to fill exactly W kg. Each packet type can be used unlimited times. Return -1 if impossible. Input: JSON {costs, W}.

Input: JSON {costs, W}.

Output: Integer or -1.

Examples

Input: {"costs":[1,2,3,4,5],"W":5}
Output: 5
Explanation: 5 packets of 1kg at cost 1 each.

Input: {"costs":[-1,-1,-1],"W":3}
Output: -1
Explanation: No packets available.

Constraints

• 1 <= costs.length <= 20
• costs[i] in {-1} ∪ [1, 10^4]
• 1 <= W <= 100

Asked by