JOI Kingdom is famous for producing gold. In JOI Kingdom, once in every year, they use a bulldozer to mine gold.

The land of JOI Kingdom is described as a plane with $xy$-coordinates. There are $N$ spots in the land. The $i$-th spot ($1 \le i \le N$) is $(X_i, Y_i)$. Each spot has either gold or rock, but not both.

If the spot $i$ has gold, when we mine it once, we obtain gold of value $V_i$. If the spot $i$ has rock, when we mine it once, we obtain rock. The cost to discard it is $C_i$.

We use a bulldozer for mining in the following way. First, we choose two parallel lines in the $xy$-plane. Then, we mine all gold and rock, once for each, in the area between two parallel lines (including gold or rock lying on them).

The profit of JOI Kingdom is the total value of gold in the area for mining minus the total cost to discard rock in the same area. We want to maximize the profit of JOI Kingdom.

Task

Write a program which calculates the maximum profit of JOI Kingdom.

Input

Read the following data from the standard input.

• The first line of input contains an integer $N$, the number of spots where we can take gold or rock.

• The $i$-th line ($1 \le i \le N$) of the following $N$ lines contains three space separated integers $X_i$, $Y_i$, $W_i$.

  • If $W_i \ge 1$, the $i$-th spot $(X_i, Y_i)$ has gold. When we mine it once, we obtain gold of value $V_i = W_i$.
  • If $W_i \le -1$, the $i$-th spot $(X_i, Y_i)$ has rock. When we mine it once, we obtain rock, and the cost to discard it is $C_i = -W_i$.

  $W_i \ne 0$ is satisfied.

Output

Write one line to the standard output. The output contains the maximum profit of JOI Kingdom.

Constraints

All input data satisfy the following conditions.

• $1 \le N \le 2\,000$.
• $-1\,000\,000\,000 \le X_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $-1\,000\,000\,000 \le Y_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
• $1 \le |W_i| \le 1\,000\,000\,000$.
• $(X_i, Y_i) \ne (X_j, Y_j)$ ($1 \le i < j \le N$).

Subtasks

There are 5 subtasks. The score and additional constraints of each subtask are as follows:

Subtask 1 [5 points]

• $N \le 100$.
• $Y_i = 0$ ($1 \le i \le N$). In other words, all spots lie on the $x$-axis.

Subtask 2 [20 points]

• $N \le 100$.
• No three distinct spots lie on a line.
• Let $L$ be a line on the $xy$-plane passing through two distinct spots. Let $L'$ be another line, different from $L$, on the $xy$-plane passing through two distinct spots. Then, $L$ and $L'$ are not parallel to each other.

Subtask 3 [35 points]

• No three distinct spots lie on a line.
• Let $L$ be a line on the $xy$-plane passing through two distinct spots. Let $L'$ be another line, different from $L$, on the $xy$-plane passing through two distinct spots. Then, $L$ and $L'$ are not parallel to each other.

Subtask 4 [20 points]

• No three distinct spots lie on a line.

Subtask 5 [20 points]

There are no additional constraints.

Examples

Input 1

5
-5 5 -2
2 5 10
1 4 -2
4 -5 4
-2 2 7

Output 1

19

Note

In Sample Input 1, the positions of gold and rock in JOI Kingdom are as follows.

In this sample input, we can take gold or rock at the spots $2$, $3$, $4$, $5$. Then the profit of JOI Kingdom is $19$. This is the maximum profit of JOI Kingdom.

Input 2

6
0 0 6
1 0 -2
2 0 8
0 1 -2
1 1 5
2 1 -2

Output 2

15

Note

In Sample Input 2, the spots $1$, $2$, $3$ lie on a line. Also, the spots $4$, $5$, $6$ lie on a line.

Input 3

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

Output 3

5

Note

In Sample Input 3, no three distinct spots lie on a line. Let $L$ be a line passing through the spots $1$ and $2$, and let $L'$ be a line passing through the spots $3$ and $4$. Then, $L$ and $L'$ are parallel to each other.

Input 4

2
0 0 -1
1 0 -1

Output 4

0

Note

It is possible to choose the area without any gold or rock. In Sample Input 4, the maximum profit is $0$.

Input 5

15
10 3 30
5 10 -17
4 -5 14
0 -3 -9
-2 3 17
6 9 -19
-9 -6 -14
-2 -3 10
-3 -3 30
8 1 -28
9 -9 -5
7 -5 -24
-8 -10 5
-7 2 20
10 -3 -13

Output 5

107