석유

석유 회사는 우물 하나를 뚫어 땅속에 묻힌 석유층에서 석유를 뽑아 올린다. 새로 찾은 석유층은 하나로 뭉쳐 있는 경우가 드물고, 보통 여러 조각으로 나뉘어 층층이 쌓여 있다.

회사는 상황을 2차원 모형으로 단순화한다. 석유층은 각각 지표면과 평행한 수평 선분이고, 우물은 지표면에서 직선으로 뚫는다. 우물은 내려가는 길에 닿는 모든 석유층에서 석유를 뽑아내며, 선분의 끝점에서 닿아도 그 석유층을 전부 뽑아낸다. 석유층이 품고 있는 석유의 양은 그 석유층의 너비와 같으므로, 우물의 채굴량은 우물이 닿는 석유층의 너비를 모두 더한 값이다.

우물은 지표면에서 아래로 뚫으므로 수평이 될 수 없다.

우물 하나로 뽑아낼 수 있는 석유의 최대량을 구하라.

그림 1: 땅속에 묻힌 석유층. 첫 번째 예제 입력에 해당한다.

첫째 줄에 석유층의 개수 $n$이 주어진다 ($1 \le n \le 2000$). 이어지는 $n$개의 줄에는 석유층 하나를 나타내는 세 정수 $x_0$, $x_1$, $y$가 주어진다. 이 석유층은 두 끝점이 $(x_0, y)$와 $(x_1, y)$인 선분이고, $y$는 지표면에서의 깊이다. 세 값은 $|x_0|, |x_1| \le 10^6$과 $1 \le y \le 10^6$을 만족한다. 서로 다른 두 석유층은 점 하나도 공유하지 않는다. $x_0$이 $x_1$보다 클 수 있고, $x_0 = x_1$인 석유층은 너비가 0이다.

우물 하나로 뽑아낼 수 있는 석유의 최대량을 정수 하나로 출력한다.