Little H has $n$ bowls that need to be placed in a cupboard, and she wants to stack them. You know that each bowl is a regular frustum (a truncated cone) that is wider at the top and narrower at the bottom. You have already measured the height and the two radii of each bowl. Please help Little H find a stacking order such that the total height of the stacked bowls is minimized. For example:

Input

The first line contains an integer $n$, representing the number of bowls. The following $n$ lines each contain three integers $h$, $r_1$, and $r_2$, representing the height and the two radii of a bowl, respectively, where $r_1 < r_2$.

Output

A single number representing the minimum height. Round the answer to the nearest integer.

Constraints

$100\%$ of the data satisfies $n \le 9$. The absolute value of all input numbers does not exceed $1000$.

Examples

Input 1

3
50 30 80
35 25 70
40 10 90

Output 1

55