i-th one costs costs[i]. Leo and Mia buy gifts together and try out different payment rules. Each rule is a pair deals[j] = [cap, m]:
- if a gift costs at most cap, Leo pays for all of it;
- otherwise Leo pays cap and Mia covers the rest.
Under the rule [cap, m] Leo picks exactly m different gifts and wants the difference "what Leo paid minus what Mia paid" to be as small as possible.
The rules are considered independently of each other. Return an array whose j-th element is the smallest possible difference for deals[j].costs=[4, 12, 7, 20], deals=[[10, 2], [6, 4]] → [4, 1]
Deal [10, 2]: Leo picks the gifts costing 4 and 20. He pays 4 for the first and 10 for the second, with Mia covering the other 10, so the gap is 14 − 10 = 4. Deal [6, 4]: every gift must be bought; Leo pays 4 + 6 + 6 + 6 = 22 and Mia pays 6 + 1 + 14 = 21, a gap of 1.
costs=[3, 9], deals=[[2, 1]] → [-5]
The gift costing 9 is the best pick: Leo pays 2 and Mia pays 7, so the gap is 2 − 7 = −5. The answer may be negative.
costs.length ≤ 10⁵costs[i] ≤ 10⁹deals.length ≤ 10⁵deals[j] = [cap, m] with 1 ≤ cap ≤ 10⁹ and 1 ≤ m ≤ costs.lengthcosts=[4, 12, 7, 20], deals=[[10, 2], [6, 4]]
[4, 1]
Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.