题目描述

小 H 有 $n$ 个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小 H 找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：

输入格式

第一行一个整数 $n$，表示碗的数目。

以下 $n$ 行，每行三个整数 $h,r_1,r_2$，分别表示碗高及上下底半径。其中 $r_1<r_2$。

输出格式

仅一个数，表示最小的高度。答案四舍五入取整。

样例

3
50 30 80
35 25 70
40 10 90

55

数据规模与约定

对于 $100\%$ 的数据，保证 $n\le 9$，且所有输入的数的绝对值均不超过 $1000$。

题目来源

[ZJOI2006]Day2