농지 나누어 갖기

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

진호는 동아리 회장과 부회장에게도 땅을 나누어 주려고 한다. 진호는 자신의 땅에서 각 변이 $x$축 또는 $y$축에 수직인 직사각형 땅을 골라, 두 부분으로 잘라 회장과 부회장에게 하나씩 준다. 회장과 부회장이 받는 땅도 각 변이 $x$축 또는 $y$축에 수직인 직사각형이어야 한다.

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

회장과 부회장은 자신이 받은 땅 안에 있는 모든 농장에 작물을 심어야 한다. 자신의 땅에 없는 농장에는 작물을 심으면 안 된다. 농장마다 심을 수 있는 작물이 다르다. $i$번 농장에 작물을 심으면 회장은 $a_i$만큼, 부회장은 $b_i$만큼의 만족감을 얻는다.

회장과 부회장이 받는 땅에 농장이 하나도 없을 수도 있다. 심을 농장이 없으면 얻는 만족감의 합은 0이다. 진호는 회장과 부회장이 더 많은 만족감을 얻기를 원한다. 두 사람이 얻을 수 있는 만족감 합의 최댓값을 구하시오.

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

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 농장의 좌표 $(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로 선언하면 오버플로가 발생할 수 있으니 주의하라.