시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 5 3 3 60.000%

문제

평면에 N(1≤N≤1,000)개의 점들이 있다. 각각의 점들은 정수 값으로 어떤 가중치 S(1≤S≤2,000,000)를 가지고 있다. 또 각각의 점들은 (r, c)의 좌표를 갖는데 이는 (행, 열) 순이다. 또한 1≤r≤2,000,000과 1≤c≤2,000,000가 성립한다.

이제 우리는 세로로 A(1≤A≤2,000,000), 가로로 B(1≤B≤2,000,000)만큼의 직사각형을 쳐서 이 중 몇 개의 점들을 이 사각형 안에 포함시키려고 한다. 이 때, 사각형 안에 포함된 점들 중, “S의 최대-S의 최소”가 최대가 되도록 하려 한다.

예를 들어 다음과 같은 경우를 보자.

9

8

2

6

1

3

5

4

이는 예제 데이터와 같은 경우고, 회색 부분처럼 선택했을 때, 가중치 최대-가중치 최소가 7이 되고 이 경우가 이 값이 최대가 되는 경우이다.

입력

첫째 줄에 세 정수 N, A, B가 주어진다. 다음 N개의 줄에는 각 점의 r(세로좌표), c(가로좌표), S(가중치)를 나타내는 세 정수가 주어진다.

출력

첫째 줄에 가중치 최대 - 가중치 최소가 될 경우의 이 값을 출력한다. 

예제 입력

8 4 2
1 4 9
1 5 8
2 10 2
3 2 6
4 6 1
5 15 3
6 4 5
7 9 4

예제 출력

7

힌트