문제
황금의 땅이라는 별명을 가진 나라가 있다. 이 나라에는 개발 되지 않은 많은 금광들이 존재한다.
이 금광들을 지도상에 표시할 때, 평면상의 점들로 표현한다.
![6218530a035dcddf80d1110aca065469_1454062510_7408.png](https://u.jungol.co.kr/problem/2798/cdf59402-f181-416a-b19b-5b21f991b2f3.png)
각 점
이
금광 개발업자는
이때 금광들을 개발하여 얻게 되는 개발 이익은 금광들의
개발업자는
예를 들어서, 위의 그림-1에서 개발 이익이 최대가 되는 영역
직사각형 모양의 땅을 사서 얻게 되는 최대 개발 이익을 출력하는 프로그램을 작성하시오.
![6218530a035dcddf80d1110aca065469_1454062563_1856.png](https://u.jungol.co.kr/problem/2798/de3ea2b4-1f59-45a0-9f48-56b0337fdd65.png)
입력
입력파일의 첫 줄에는 금광들의 개수
이어지는
금광의 좌표는 모두 서로 다르며
출력
출력은 한 줄로 이루어진다. 금광 개발업자가 직사각형 모양의 땅
계산 과정에서 32비트 정수 변수가 표현할 수 있는 범위를 넘어서 64비트 정수 변수 (long long type)를 사용해야 할 수도 있음에 주의하라.
부분문제
번호 | 점수 | 조건 |
---|---|---|
#1 | 11점 | |
#2 | 23점 | |
#3 | 9점 | |
#4 | 15점 | 모든 점들에 대해서 |
#5 | 42점 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
예제1
7
2 8 2
5 5 3
3 3 -1
10 2 5
9 7 -2
6 7 -1
7 3 -1
7
예제2
10
4 9 2
6 10 -1
6 8 3
5 6 5
8 5 10
7 6 -7
9 10 4
20 1 1
10 8 6
10 6 -5
18