Migrated from Lutece 3055 取线段

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在二维平面上，有$n$条水平线段，如图。任意画一条直线，会有若干条线段与之相交（交点可以是线段端点）。 例如，直线①与三条线段相交，长度分别为6、10、6，与之相交的线段总长为22；直线②与四条线段相交，长度分别为5、7、5、3，与之相交的线段总长为20。 现在，Reese想知道，任一条非水平的直线，与之相交的线段总长度最长可以是多少。

Input

第一行一个整数 $n$ ，代表线段数。 第二至 $n+1$ 行，每行 $3$ 个整数 $x_0 , x_1 , y$，表示线段的两个端点 $( x_0 , y )$，$( x_1 , y )$。

Output

一行一个整数表示与同一条直线相交的线段总长度的最大值。

Samples

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

25

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

200

Constraints

$1 \leq n \leq 2000$ , $|x_0|, |x_1| \leq 10^6$ , $1 \leq y \leq 10^6$. 数据保证不会有两条线段相交，也不会有两条线段共用一个端点。

Resources

2023 UESTC ICPC Training for Geometry