[ICPC2016 WF] Oil

### 题目描述 世界经济的很大一部分依赖于石油，这就是为什么对发现和开采石油的新方法的研究仍然活跃。石油公司的利润在一定程度上取决于他们能够多么有效地钻探石油。国际原油石油联盟（ICPC）希望通过广泛的计算机模拟来更容易地确定如何以最佳方式钻探油井。 每天钻探油井变得越来越困难，因为新发现的油藏通常不是一个整体，而是分裂成许多部分。ICPC目前关注的是分层沉积物。 为了简化其分析，ICPC只考虑二维情况，其中油藏被建模为与地球表面平行的水平线段。ICPC想知道如何放置一个单独的油井以提取最大量的石油。油井沿着一条直线从地面钻井，并可以从其下降的路径上相交的所有沉积物中提取石油，即使相交点位于沉积物的端点处。图G.1中显示了一个这样的井，击中三个沉积物。在这个简单的模型中，一个沉积物中含有的石油量等于该沉积物的宽度。你能帮助ICPC确定通过一个单井可以提取的最大石油量吗？ ### 输入格式 输入的第一行包含一个整数 $n (1\le n\le 2000)$，表示油田的数量。 接下来的 $n$ 行，每行描述一个沉积物。这些行包含三个整数 $x_0、x_1$ 和 $y$，表示沉积物的位置为线段，其端点为 $(x_0,y)$ 和 $(x_1,y)$。这些数字满足 $|x_0|,|x_1|≤10^6$。没有两个沉积物会相交，甚至不会在一点相交。 ### 输出格式 输出一个整数，表示单个油井可以提取的最大石油量。

A large part of the world economy depends on oil, which is why research into new methods for finding and extracting oil is still active. Profits of oil companies depend in part on how efficiently they can drill for oil. The International Crude Petroleum Consortium (ICPC) hopes that extensive computer simulations will make it easier to determine how to drill oil wells in the best possible way. Drilling oil wells optimally is getting harder each day – the newly discovered oil deposits often do not form a single body, but are split into many parts. The ICPC is currently concerned with stratified deposits, as illustrated in Figure G.1. To simplify its analysis, the ICPC considers only the 2-dimensional case, where oil deposits are modeled as horizontal line segments parallel to the earth’s surface. The ICPC wants to know how to place a single oil well to extract the maximum amount of oil. The oil well is drilled from the surface along a straight line and can extract oil from all deposits that it intersects on its way down, even if the intersection is at an endpoint of a deposit. One such well is shown as a dashed line in Figure G.1, hitting three deposits. In this simple model the amount of oil contained in a deposit is equal to the width of the deposit. Can you help the ICPC determine the maximum amount of oil that can be extracted by a single well?

The first line of input contains a single integer n ($1 ≤ n ≤ 2 000$), which is the number of oil deposits. This is followed by $n$ lines, each describing a single deposit. These lines contain three integers $x_0$, $x_1$, and y giving the deposit’s position as the line segment with endpoints $(x_0, y)$ and $(x_1, y)$. These numbers satisfy $|x_0|, |x_1| ≤ 10^6$ and $1 ≤ y ≤ 10^6$ . No two deposits will intersect, not even at a point.

Display the maximum amount of oil that can be extracted by a single oil well.

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

200

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

25