Bulldozer

We are given N points on the plane. For each point i (1 ≤ i ≤ N), its coordinates are \((X_i, Y_i)\) and its weight is a nonzero integer \(W_i\) (which may be negative). Two parallel lines are drawn arbitrarily in the plane. The total value is defined as the sum of the weights of all points that lie between the two lines (points on the boundaries are included). Your task is to choose two parallel lines (i.e. choose a "strip") so that the total value of the points inside is maximized. Note that one is allowed to have an empty strip (by choosing the two lines arbitrarily close to each other) in which case the total value is 0. Output the maximum achievable total value.

Mathematical formulation:

For any unit vector \((\cos\theta, \sin\theta)\), each point \((x,y)\) has a projection value \(t=x\cos\theta+y\sin\theta\). Then by choosing two real numbers \(a\) and \(b\) (with \(a\le b\)) the strip is defined as the set of points satisfying \(a\le x\cos\theta+y\sin\theta\le b\) and its value is \(\sum_{i: a\le X_i\cos\theta+Y_i\sin\theta\le b} W_i\). The answer is the maximum total value over all choices of \(\theta\) and \([a,b]\). It can be shown that an optimal solution always exists and the answer is an integer.

inputFormat

The input is given in the following format:

N
X_1 Y_1 W_1
X_2 Y_2 W_2
... 
X_N Y_N W_N

Here, N is the number of points. Each of the next N lines contains three integers representing the coordinates and weight of a point.

outputFormat

Output one integer, the maximum total value that can be achieved by choosing two parallel lines to form a strip on the plane.

sample

4
0 0 5
1 0 -3
0 1 7
1 1 -2

12