1069. Filling the Most Bags

n bags are given. Bag i currently holds cur[i] stones and its capacity is cap[i], with cur[i] <= cap[i]. You hold extra loose stones and may put any of them into any bags.

Print the largest number of bags you can bring to exactly full.

extra=2, cur 2 3 4, cap 3 6 7 -> 1 extra=10, cur 0 0 0 0, cap 1 2 3 4 -> 4 extra=0, cur 5, cap 5 -> 1 already full extra=0, cur 4, cap 5 -> 0

## What most people try first

A subset-sum table over extra, which reaches 10^14. Or every subset of the bags, which is 2^n and is the brute force this problem was checked against on at most sixteen bags.

Both are answering a harder question than the one asked. The VALUE of a filled bag is 1 whatever its size, which is exactly the condition under which a knapsack collapses to a sort.

## Sort the deficits

need[i] = cap[i] - cur[i] sort need ascending count = 0 for each d in need: if extra < d: stop extra -= d count += 1

A bag already full has need = 0, costs nothing, and is counted for free, which the sorted sweep handles without a special case because zeros sort to the front.

## Why the smallest deficits first

Suppose some choice of k bags can all be filled, so their deficits total at most extra. Compare those k deficits with the k smallest deficits overall, in sorted order: the jth smallest overall is at most the jth smallest of that particular set, so the k smallest total no more and also fit within extra.

So whenever k bags are fillable, the k cheapest bags are fillable, and the longest sorted prefix that fits is the answer.

This is the same lemma as problem #1045, where prices replaced deficits, and the mirror of #1051, where the largest counts were taken instead of the smallest. Three problems, one exchange.

## The stop, not skip

Once a deficit does not fit, no later one does either, since they are sorted. Skipping it and trying the next is not merely wasteful, it produces a wrong answer if the list is not actually sorted, which is exactly the bug that hides when the input happens to arrive in order.

## Overflow

extra reaches 10^14 and a capacity reaches 10^9, so the total of n deficits reaches 10^14 as well. The signed 32 bit limit is 2147483647, so extra alone overflows a 32 bit read, and the short test with three bags of 10^9 and extra = 3 * 10^9 catches it.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ extra ≤ 100000000000000` - `0 ≤ cur[i] ≤ cap[i] ≤ 1000000000`