You are given five integers cost1, cost2, costBoth, need1, and need2.

There are three types of items available:

• An item of type 1 costs cost1 and contributes 1 unit to the type 1 requirement only.
• An item of type 2 costs cost2 and contributes 1 unit to the type 2 requirement only.
• An item of type 3 costs costBoth and contributes 1 unit to both the type 1 and type 2 requirements.

You must collect enough items so that:

• The total contribution toward type 1 is at least need1.
• The total contribution toward type 2 is at least need2.

In other words, you need to satisfy two separate requirements at the same time. Type 1 and type 2 items each help with only one requirement, while a type 3 item is more flexible because a single purchase counts toward both requirements simultaneously.

Your goal is to choose how many of each item type to buy so that both requirements are met, while spending as little money as possible.

Return an integer representing the minimum possible total cost to achieve these requirements.

The key observation is that a type 3 item is special: one purchase satisfies one unit of both requirements at the same time. So the whole decision comes down to figuring out how many type 3 items to buy, and then filling in the rest with cheaper single-type items.

Let's think about the trade-offs. If we buy a type 3 item to cover one unit of both need1 and need2, it costs costBoth. The alternative way to cover one unit of each requirement separately is to buy one type 1 item and one type 2 item, costing cost1 + cost2. This tells us that type 3 items are only worth buying as long as both requirements still have remaining units to satisfy. Once one requirement is fully met, a type 3 item would "waste" half its value on a requirement that's already done.

This reasoning naturally splits the possibilities into a few clean cases:

1. Never use type 3. Simply buy need1 type 1 items and need2 type 2 items. The cost is need1 * cost1 + need2 * cost2.

2. Use type 3 to cover everything. Since each type 3 item covers one unit of both requirements, we need enough of them to satisfy the larger requirement. Buying max(need1, need2) type 3 items covers both needs completely. The cost is costBoth * max(need1, need2).

3. Use type 3 only while both requirements overlap. Let mn = min(need1, need2). We use mn type 3 items to knock out the shared portion of both requirements, then cover whatever is left of the larger requirement with the matching single-type items. The cost is costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2.

Why are these three cases enough? Because the cost as a function of "number of type 3 items used" is linear within the meaningful range, so the best choice always lands at one of the boundary points: using zero type 3 items, using just enough to cover the overlap (min), or using enough to cover everything (max). The optimal answer must be one of these endpoints, so we just compute all three and take the minimum among them.

Pattern Learn more about Greedy and Math patterns.

We use case analysis to directly compute the cost of each candidate strategy, then take the minimum. No loops or extra data structures are needed — just a few arithmetic expressions based on the three boundary cases identified in the intuition.

Case 1 — Only buy Type 1 and Type 2 items.

We ignore type 3 entirely and satisfy each requirement on its own:

a = need1 * cost1 + need2 * cost2

Case 2 — Only buy Type 3 items.

Each type 3 item covers one unit of both requirements, so we need as many as the larger requirement to fully cover both:

b = costBoth * max(need1, need2)

Case 3 — Buy Type 3 items for the overlap, then fill the rest.

Let mn = min(need1, need2). We use mn type 3 items to cover the shared portion of both requirements, then buy single-type items for whatever remains on each side:

c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2

Notice that exactly one of (need1 - mn) or (need2 - mn) will be zero (whichever requirement is the smaller one), so only the leftover of the larger requirement actually contributes to the cost.

Final answer.

We return the smallest of the three computed costs:

return min(a, b, c)

In the implementation, these map directly to the variables in the code:

a = need1 * cost1 + need2 * cost2
b = costBoth * max(need1, need2)
mn = min(need1, need2)
c = costBoth * mn + (need1 - mn) * cost1 + (need2 - mn) * cost2
return min(a, b, c)

Since every step is a constant number of arithmetic operations, the time complexity is O(1) and the space complexity is O(1).