불도저

JOI Kingdom은 금 생산으로 유명하다. JOI 왕국에서는 해마다 한 번 불도저를 사용하여 금을 채굴한다. JOI Kingdom의 땅은 xy좌표가 있는 평면으로 나타낸다. 이 땅에는 N개의 지점이 있다. i번째 지점은 (1 ≤ i ≤ N) (Xi , Yi )이다. 각 지점에는 금과 암석 중 정확히 하나만 있다. 지점 i에 금이 있다면, 그곳을 한 번 채굴할 때 가치가 Vi인 금을 얻는다. 지점 i에 암석이 있다면, 그곳을 한 번 채굴할 때 암석을 얻는다. 이를 폐기하는 비용은 Ci이다. 불도저를 사용하여 다음과 같은 방법으로 채굴한다. 먼저 xy평면에서 서로 평행한 두 직선을 고른다. 그런 다음 두 평행선 사이의 영역에 있는 모든 금과 암석을 각각 한 번씩 채굴한다. 두 직선 위에 있는 금이나 암석도 포함한다. JOI Kingdom의 이익은 채굴 영역에 있는 금의 가치 총합에서 같은 영역에 있는 암석의 폐기 비용 총합을 뺀 값이다. 우리는 JOI Kingdom의 이익을 최대화하고자 한다.

JOI Kingdom의 최대 이익을 계산하는 프로그램을 작성하라.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ N ≤ 2 000.

• −1 000 000 000 ≤ Xi ≤ 1 000 000 000 (1 ≤ i ≤ N).

• −1 000 000 000 ≤ Yi ≤ 1 000 000 000 (1 ≤ i ≤ N).

• 1 ≤ |Wi | ≤ 1 000 000 000.

• (Xi , Yi ) , (X j , Y j ) (1 ≤ i < j ≤ N).

부분 과제

부분 과제는 5개이다. 각 부분 과제의 점수와 추가 제약 조건은 다음과 같다.

부분 과제 1 [5점] • N ≤ 100.

• Yi = 0 (1 ≤ i ≤ N). 다시 말해, 모든 지점은 x축 위에 있다.

부분 과제 2 [20점] • N ≤ 100.

• 서로 다른 세 지점이 한 직선 위에 놓이는 경우는 없다.

• xy평면에서 서로 다른 두 지점을 지나는 직선을 L이라 하자. xy평면에서 서로 다른 두 지점을 지나며 L과 다른 또 하나의 직선을 L′이라 하자. 그러면 L과 L′은 서로 평행하지 않다.

부분 과제 3 [35점] • 서로 다른 세 지점이 한 직선 위에 놓이는 경우는 없다.

• xy평면에서 서로 다른 두 지점을 지나는 직선을 L이라 하자. xy평면에서 서로 다른 두 지점을 지나며 L과 다른 또 하나의 직선을 L′이라 하자. 그러면 L과 L′은 서로 평행하지 않다.

부분 과제 4 [20점] • 서로 다른 세 지점이 한 직선 위에 놓이는 경우는 없다.

부분 과제 5 [20점] 추가 제약 조건은 없다.

표준 입력에서 다음 데이터를 읽는다.

• 입력의 첫째 줄에는 금이나 암석을 채굴할 수 있는 지점의 수를 나타내는 정수 N이 주어진다.

• 이어지는 N개 줄 중 i번째 줄에는 (1 ≤ i ≤ N) 공백으로 구분된 세 정수 Xi , Yi , Wi 가 주어진다.

– Wi ≥ 1이면, i번째 지점 (Xi , Yi )에는 금이 있다. 그곳을 한 번 채굴하면 가치가 Vi = Wi 인 금을 얻는다. – Wi ≤ −1이면, i번째 지점 (Xi , Yi )에는 암석이 있다. 그곳을 한 번 채굴하면 암석을 얻으며, 이를 폐기하는 비용은 Ci = −Wi 이다.

Wi , 0을 만족한다.

표준 출력에 한 줄을 출력한다. 출력에는 JOI Kingdom의 최대 이익이 주어진다.