Jenny works at BBB (Battery Bank of Brazil). She's in charge of optimizing the batteries' displacements, but can't solve the problem. Knowing you are a programmer, she asked for your help.

At BBB, the batteries are arranged in piles. In a bank, the batteries can't be discharged. So, when recharging then, the bank spends M energy units, where M is the size of the greatest pile. Each pile initially has a_i batteries.

There is a machine the can move a battery from pile i to pile j with cost b_i + c_j. Jenny has a limited budget of K for moving the batteries and the bank wants the minimum M possible at the end.