Optimal Oil Well Drilling

The International Crude Petroleum Consortium (ICPC) is trying to maximize the oil extraction by optimally placing a single oil well. In a simplified 2-dimensional model, oil deposits are represented as horizontal line segments (parallel to the earth's surface). Each deposit i is given by a line segment at depth y_i spanning from L_i to R_i (with L_i < R_i). The amount of oil in a deposit equals its width R_i - L_i.

An oil well is drilled from the surface (assume y = 0) along a straight line (which can be non‐vertical) and will extract oil from every deposit that it touches. A deposit is touched if the drilling line intersects the deposit (touching an endpoint counts). If the well is described by the equation:

x = X + t * y (where t = tan(θ))

then it touches deposit i (at depth y_i) if:

L_i ≤ X + t · y_i ≤ R_i

Your task is to choose X and t optimally so that the sum of widths of the deposits hit (i.e. the total extracted oil) is maximized. Note that you are free to choose any real numbers X and t.

Hint: For a fixed slope t, each deposit i yields a constraint on X: X must lie in the interval [L_i - t · y_i, R_i - t · y_i]. Then the problem reduces to finding a point X which lies in as many of these intervals (weighted by deposit width) as possible. The overall maximum can be obtained by testing suitable candidate slopes (e.g. those obtained when the drilling line touches boundaries of two deposits simultaneously).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 100), the number of deposits. Each of the next n lines contains three space-separated integers: y, L, and R (with L < R). Here, y (y > 0) is the depth of the deposit, and the deposit spans horizontally from L to R.

outputFormat

Output a single integer, the maximum total amount of oil that can be extracted by a single well. (For each deposit, the extracted oil is its width: R - L.)

sample

3
1 1 5
2 2 7
3 4 6

11