31940번 - 농지 나누어 갖기

문제

평소 농지 가꾸기 동아리 활동을 좋아하는 진호는 농사에 필요한 땅을 매입했다. 진호는 자신이 매입한 땅에 있는 $N$개의 농장에 각각 1ドル$번부터 $N$번까지 번호를 붙였다. 각 농장은 좌표평면 위의 점으로 표현했을 때 $x$좌표와 $y$좌표가 모두 정수인 좌표에 있다.

진호는 농지 가꾸기 동아리의 회장과 부회장에게도 땅을 나누어 주려고 한다. 진호는 자신의 땅에서 각 변이 $x$축 또는 $y$축에 수직인 직사각형 모양의 땅을 적당히 선택한 후, 그 땅을 두 부분으로 잘라 회장과 부회장에게 하나씩 나누어 주려고 한다. 이러한 과정을 통해서 회장과 부회장이 받는 땅 역시 각 변이 $x$축 또는 $y$축에 수직인 직사각형 모양이어야 한다.

$N$개의 농장은 각 직사각형의 내부 또는 외부에 있어야 한다. 즉, 회장과 부회장이 갖게 될 땅의 경계에는 농장이 있으면 안 된다. 회장과 부회장이 갖게 될 땅의 각 꼭짓점이 정수 좌표일 필요는 없다.

회장과 부회장은 자신이 받게 될 땅에 있는 모든 농장에 작물을 심어야 한다. 자신의 땅에 있지 않은 농장에는 작물을 심어서는 안 된다. 각 농장에는 심을 수 있는 작물이 다르며, $i$번 농장에서 작물을 심을 때 회장은 $a_i$만큼, 부회장은 $b_i$만큼의 만족감을 얻는다.

회장과 부회장이 받게 될 땅에 농장이 없을 수도 있다. 작물을 심을 농장이 없는 경우 얻는 만족감의 합은 0ドル$이다. 진호는 회장과 부회장이 더 많은 만족감을 얻기를 원한다. 회장과 부회장이 작물을 심어 얻을 수 있는 만족감의 합의 최댓값을 구해 보자.

입력

첫째 줄에 농장의 개수 $N$이 주어진다. $(1 \le N \le 2 000)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 농장의 좌표 $\left( x_i , y_i \right)$를 나타내는 두 수 $x_i,ドル $y_i$와 회장과 부회장의 만족감 $a_i,ドル $b_i$가 공백으로 구분되어 주어진다. $( -{10}^9 \le x_i , y_i , a_i , b_i \le {10}^9)$

모든 농장의 좌표는 서로 다르다. 입력으로 주어지는 모든 수는 정수이다.

출력

회장과 부회장이 얻을 수 있는 만족감의 합의 최댓값을 출력한다.

제한

노트

C/C++, Java 등의 언어에서 일부 변수를 int로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.