Vương quốc JOI nổi tiếng về vàng. Lãnh thổ được biểu diễn trên mặt phẳng tọa độ, với \(N\) địa điểm. Địa điểm thứ \(i\) nằm tại \((X_i,Y_i)\) và chứa vàng hoặc đá, nhưng không chứa cả hai.

Nếu địa điểm chứa vàng, khai thác một lần thu được vàng trị giá \(V_i\). Nếu chứa đá, khai thác một lần phải trả chi phí \(C_i\) để xử lý đá.

Để khai thác, trước hết chọn hai đường thẳng song song, rồi khai thác một lần toàn bộ vàng và đá trong miền nằm giữa hai đường, kể cả trên hai đường biên. Lợi nhuận bằng tổng giá trị vàng trừ tổng chi phí xử lý đá trong miền. Có thể chọn một miền không chứa địa điểm nào.

Hãy tính lợi nhuận lớn nhất.

Dữ liệu vào

• Dòng đầu chứa \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(X_i,Y_i,W_i\). Nếu \(W_i\ge1\), địa điểm chứa vàng trị giá \(V_i=W_i\); nếu \(W_i\le-1\), địa điểm chứa đá với chi phí \(C_i=-W_i\).

Dữ liệu ra

In lợi nhuận lớn nhất.

Ràng buộc

• \(1\le N\le 2\,000\).
• \(-1\,000\,000\,000\le X_i,Y_i\le1\,000\,000\,000\).
• \(1\le |W_i|\le1\,000\,000\,000\).
• Không có hai địa điểm trùng nhau.

Phân nhóm

1. \(5\) điểm: \(N\le100\) và \(Y_i=0\) với mọi \(i\)
2. \(20\) điểm: \(N\le100\); không có ba điểm phân biệt thẳng hàng; hai đường thẳng khác nhau cùng đi qua hai điểm của dữ liệu không song song
3. \(35\) điểm: Không có ba điểm phân biệt thẳng hàng; hai đường thẳng khác nhau cùng đi qua hai điểm của dữ liệu không song song
4. \(20\) điểm: Không có ba điểm phân biệt thẳng hàng
5. \(20\) điểm: Không có ràng buộc bổ sung

Ví dụ

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

19

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

15

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

5

2
0 0 -1
1 0 -1

0

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

107

Nguồn

JOI 2016/2017 Open Contest.