## Solution:

For each product, we will buy exactly $a_i$ items. We will not buy more items. So, the total number items we buy will not change (because the purpose to buy more is discount, but the benefit of discount is same with the cost of one item).

So, the problem is transferred to put each item to each position. If the b is less than the index, then this item can get discount.

For example, the sample 2:

So, we know that, for b=4, index need to greater than 5. For b=2, index need to greater than 3. So, we need some items to fill in the positions of subscripts 1, 2, and 4. Obviously, we choose the item with largest b to do this.

We consider whether we can get a discount for products one by one from small to large by filling some product with higher b.

## Code:

Java

C++