As you know, some bunnies are good bunnies, and some bunnies are bad bunnies.</p>

You are given the location of all the bunnies, and their “goodness” weight (a positive integer for good bunnies and a negative integer for bad bunnies). No two bunnies are at the same location. Divide them into two groups using a straight line such that the sum of the “goodness” of the bunnies on one side of the line is as large as possible. A bunny on the line is counted in the sum of the weights on both sides of the line.

입력 형식

The first line contains N (2 ≤ N ≤ 4000), the number of bunnies. The next N lines contain three space-separated integers: x_i y_i w_i, which indicates that at the point (x_i, y_i) there is a bunny with a goodness weight of w_i (−1 000 000 ≤ x_i ≤ 1 000 000; −1 000 000 ≤ y_i ≤ 1 000 000; −10 000 ≤ w_i ≤ 10 000). The locations (x_i, y_i) will be distinct (i.e., there is no other j ≠ i such that (x_i, y_i) = (x_j, y_j)).

출력 형식

Output the maximum sum of weights that is possible by drawing a straight line and picking all the bunnies which are on one side of that line.

예제 입력

6
1 8 4
1 4 6
7 7 2
4 10 -3
4 6 -9
4 2 8

예제 출력

18