P6771 [USACO05MAR] Space Elevator Space Elevator.

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.

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.

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

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