Space Elevator

Cows are going to space! They plan to build a space elevator using blocks. You are given \(N\) types of blocks. The \(i\)-th type of block has a height \(h_i\), an available quantity \(c_i\), and a maximum allowed height \(a_i\) such that no part of this block can exceed \(a_i\) when it is used (i.e. if the block is placed on top of a tower with current height \(H\), then it must hold that \(H + h_i \le a_i\)). Your task is to choose and stack these blocks in any order to build the tallest possible space elevator.

inputFormat

The first line contains an integer \(N\) representing the number of block types. Each of the next \(N\) lines contains three integers \(h_i\), \(c_i\), and \(a_i\) — the height of the block, the number of blocks available of that type, and the maximum height limit for any part of that block, respectively.

outputFormat

Output a single integer, the maximum height of the space elevator that can be built under the given constraints.

sample

1
5 3 10

10