시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 512 MB 44 15 15 36.585%

문제

세계의 경제는 석유에 의존하고, 그것이 아직 남아있는 석유를 찾고 시추하는 방법을 개발하는 이유다. 정유회사의 수익은 얼마나 효율적으로 땅을 파야하는지에 달려있다. The International Crude Petroleum Consortium(ICPC)는 폭넓은 컴퓨터 시뮬레이션을 이용하여 얼마나 기름을 가능한 한 좋게 시추 할 수 있나 결정하려 한다.

새로 발견되는 석유는 하나로 뭉쳐있지 않고, 여러 갈래로 나뉘어져 있기 때문에 석유를 시추하는건 날이 가면 갈수록 어려워진다. ICPC는 현재 그림 G.1. 처럼 땅에 있는 석유 단층을 다루고 있다.

그림 G.1 : 땅에 뭍혀있는 석유 단층이다. 예제 입력 1과 같은 그림이다.

간단하게 분석하면, ICPC는 오직 석유 매장량과 평면만을 고려하여 지구 표면과 수평인 선분들을 그린다. ICPC는 하나의 시추 드릴에서 가장 최대의 석유를 뽑아내고 싶어한다. 석유는 지면으로부터 직선으로 시추되고, 드릴과 석유의 모든 교차점에서 시추가 가능하다. 심지어 석유층의 끝과 드릴이 닿아도 시추가 가능하다. 

한가지 예가 그림G.1과 같이 3개의 단층과 맞닿았다. 석유의 양은 좌우 넓이와 일치한다. 당신은 ICPC 가 하나의 시추드릴로 가장 많은 양의 석유를 시추할 수 있게 도와줄 수 있는가?

입력

입력의 첫 줄에는 석유층의 갯수인 정수 n (1 ≤ n ≤ 2 000) 이 입력된다.

다음 n개의 라인에는 각각의 석유 위치가 오게 되는데 각 줄은 3가지 정수 x0, x1 그리고  y 를 입력받게 된다. 석유위치는 (x0, y) 부터 (x1, y) 까지 위치하게 된다.

각 x0, x1 ,y는 |x0|, |x1| ≤ 10^6,  1 ≤ y ≤ 10^6 을 만족하며 석유는 서로 만나지 않으며 석유층의 끝끼리도 마주치지 않는다.

출력

하나의 시추드릴로 뽑을수 있는 최대 석유양을 출력하시오.

예제 입력

5
100 180 20
30 60 30
70 110 40
10 40 50
0 80 70

예제 출력

200

예제 입력 2

3
50 60 10
-42 -42 20
25 0 10

예제 출력 2

25

힌트

출처

ACM-ICPC > World Finals > 2016 World Finals G번