책 쌓기

질량이 m_i, 길이가 2, 높이가 h인 직사각형 N개가 있다. 이 직사각형들은 2차원 평면에 다음 조건을 만족하도록 쌓여 있다.

• 모든 직사각형의 변은 좌표축에 평행하다.
• 직사각형 아랫변의 y좌표는 모두 다르며, 각각 0, h, 2h, 3h, ..., (N-1)h이다.
• 가장 아래에 있는 직사각형의 왼쪽 아래 좌표는 (-2, 0), 오른쪽 아래 좌표는 (0, 0)이다.

직사각형의 x중심은 그 아랫변의 중점이다.

하나 이상의 직사각형으로 이루어진 집합의 무게중심은 각 직사각형의 x중심과 질량을 이용해 다음과 같이 계산한다.

[ \text{무게중심} = \frac{\sum_i m_i \cdot (\text{직사각형 } i\text{의 x중심})}{\sum_i m_i} ]

위에 하나 이상의 직사각형이 있는 모든 직사각형 A에 대해, A 위에 있는 모든 직사각형의 무게중심과 A의 x중심 사이의 거리가 1 이하이면 안정한 쌓기라고 한다.

직사각형을 안정하게 쌓으면 무너지지 않는다. 왼쪽 그림은 안정한 배치가 아니다. 가장 위의 두 직사각형의 무게중심과 바로 아래 직사각형의 x중심 사이의 거리가 1을 넘기 때문이다. 오른쪽 그림은 안정한 쌓기이다.

모든 직사각형의 질량이 주어졌을 때, 입력으로 주어진 순서대로 아래에서 위로 쌓으면서 안정한 쌓기가 되도록 배치한다. 이때 모든 직사각형의 오른쪽 꼭짓점 중 x좌표의 최댓값을 구하시오.

첫째 줄에 직사각형의 개수 N이 주어진다. (2 <= N <= 300,000)

다음 N개 줄에는 아래 직사각형부터 위 직사각형까지 순서대로 각 직사각형의 질량이 하나씩 주어진다. 질량은 10,000 이하의 양의 정수이다.

안정하게 쌓는 방법 중 모든 오른쪽 꼭짓점의 x좌표가 최대가 될 때의 값을 출력한다. 정답과의 절대 또는 상대 오차는 0.000001까지 허용된다.