404773: GYM101628 J Jenny and the Batteries

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.

The first line of input consists of the integers N and K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10¹⁸). The following N lines contain a_i, b_i and c_i (0 ≤ a_i, b_i, c_i ≤ 10⁶).

Print the minumum M possible.

5 20
5 3 8
2 8 3
3 2 4
7 2 1
6 1 1

5