For technical reasons, some programming languages (Kotlin, C #) will not be available during round 877.
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Bowls

time limit per test

2 secondsmemory limit per test

64 megabytesinput

input.txtoutput

output.txtOnce Petya was in such a good mood that he decided to help his mum with the washing-up. There were *n* dirty bowls in the sink. From the geometrical point of view each bowl looks like a blunted cone. We can disregard the width of the walls and bottom. Petya puts the clean bowls one on another naturally, i. e. so that their vertical axes coincide (see the picture). You will be given the order in which Petya washes the bowls. Determine the height of the construction, i.e. the distance from the bottom of the lowest bowl to the top of the highest one.

Input

The first input line contains integer *n* (1 ≤ *n* ≤ 3000). Each of the following *n* lines contains 3 integers *h*, *r* and *R* (1 ≤ *h* ≤ 10000, 1 ≤ *r* < *R* ≤ 10000). They are the height of a bowl, the radius of its bottom and the radius of its top. The plates are given in the order Petya puts them on the table.

Output

Output the height of the plate pile accurate to at least 10^{ - 6}.

Examples

Input

2

40 10 50

60 20 30

Output

70.00000000

Input

3

50 30 80

35 25 70

40 10 90

Output

55.00000000

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 23:42:06 (c3).

Desktop version, switch to mobile version.

User lists

Name |
---|