Problem Description

The cows are going to space. They plan to build a space elevator using blocks. There are $N$ types of blocks. Type $i$ has a fixed height $h_i$ and a certain quantity $c_i$. To prevent cosmic rays from damaging the blocks, no part of any block of type $i$ may exceed height $a_i$.
Please use these blocks to stack the tallest possible space elevator.

Input Format

The first line contains an integer $N$.
Lines $2$ to $N+1$: the $(i+1)$-th line contains three integers $h_i, a_i, c_i$, separated by spaces.

Output Format

One line containing one integer: the height of the space elevator.

3
7 40 3
5 23 8
2 52 6

48

Hint

Constraints for $100\%$ of the testdata: $1 \le N \le 400$, $1 \le h_i \le 100$, $1 \le c_i \le 10$, $1 \le a_i \le 4 \times 10^4$.

Translated by ChatGPT 5