시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 87 45 43 51.807%

문제

평면에 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의 최소”가 최대가 되도록 하려 한다.

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

7

출처

  • 문제의 오타를 찾은 사람: lyzqm