0/320

00:00:00

Description

Editorial

Bundle Deal Optimizer

MEDIUM25 pts

You are developing a cost optimization system for an online marketplace. The marketplace sells n distinct products, each with its own individual unit price. Additionally, the marketplace offers various bundle deals (promotional packages) that allow customers to purchase combinations of multiple products at a discounted bundled price.

Your task is to determine the minimum total cost required to purchase exactly the specified quantities of each product, making optimal use of the available bundle deals.

Input Details:

You are given an integer array price where price[i] represents the individual unit cost of the i-th product.
You are given a 2D integer array special representing the available bundle deals. Each bundle special[i] has length n + 1:
- special[i][0] through special[i][n-1] specify the quantity of each product included in this bundle.
- special[i][n] (the last element) is the total discounted price for this bundle.
You are given an integer array needs where needs[i] represents the exact quantity of the i-th product you need to purchase.

Rules and Constraints:

You must purchase exactly the quantities specified in needs — no more, no less.
You cannot purchase more items than required, even if doing so would reduce the total cost.
Each bundle deal can be used any number of times (including zero times).
You may also purchase individual items at their unit prices to fulfill remaining quantities.

Return the minimum cost required to fulfill the exact purchase requirements.

Example

Input

price = [2,5]
special = [[3,0,5],[1,2,10]]
needs = [3,2]

Output

14

Explanation

There are two products, Product A (price $2) and Product B (price $5). You need 3 units of A and 2 units of B.

Bundle 1 offers 3 units of A for $5 (a savings compared to 3 × $2 = $6). Bundle 2 offers 1 unit of A and 2 units of B for $10.

Optimal strategy: Use Bundle 2 once (getting 1A + 2B for $10), then buy 2 more units of A individually ($2 × 2 = $4). Total cost: $10 + $4 = $14.

Example

Input

price = [2,3,4]
special = [[1,1,0,4],[2,2,1,9]]
needs = [1,2,1]

Output

11

Explanation

There are three products with prices $2, $3, and $4 respectively. You need 1 unit of Product A, 2 units of Product B, and 1 unit of Product C.

Bundle 1 offers 1A + 1B for $4. Bundle 2 offers 2A + 2B + 1C for $9.

Note: Although Bundle 2 includes exactly 1C and 2B, it also includes 2A, which exceeds your requirement of 1A. You cannot use this bundle.

Optimal strategy: Use Bundle 1 once (1A + 1B for $4), then buy 1B at $3 and 1C at $4 individually. Total cost: $4 + $3 + $4 = $11.

Example

Input

price = [5]
special = [[2,8]]
needs = [4]

Output

16

Explanation

There is only one product priced at $5 per unit, and you need 4 units.

The bundle offers 2 units for $8 (instead of 2 × $5 = $10).

Optimal strategy: Use the bundle twice, getting 4 units total for 2 × $8 = $16.

This is better than buying 4 individual units at $5 each ($20).

Accepted0/0·0% Acceptance

Constraints

n == price.length == needs.length
1 ≤ n ≤ 6
0 ≤ price[i], needs[i] ≤ 10
1 ≤ special.length ≤ 100
special[i].length == n + 1
0 ≤ special[i][j] ≤ 50
Each bundle contains at least one product (at least one of special[i][0] to special[i][n-1] is non-zero).

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

needs =

[3,2]

price =

[2,5]

special =

[[3,0,5],[1,2,10]]

Bundle Deal Optimizer

Hints

Bundle Deal Optimizer

Hints