점 고르기
시간 제한2초메모리 제한128 MB
가중치가 있는 2차원 평면의 점들에 대해 고정된 크기의 축 정렬 직사각형을 배치해 포함된 점들의 최대-최소 가중치 차이를 최대화하는 문제입니다.
문제
평면 위에 N개의 점이 있다. 각 점은 정수 가중치 S를 가지며, 좌표는 (r, c)로 주어진다. 여기서 r은 행, c는 열이다.
세로 길이가 A, 가로 길이가 B인 축에 평행한 직사각형을 하나 놓아 그 안에 들어가는 점들을 선택하려고 한다. 정수 좌표에서 같은 직사각형 안에 함께 들어갈 수 있는 두 점은 행 좌표의 차이가 A보다 작고, 열 좌표의 차이가 B보다 작아야 한다.
직사각형 안에 들어간 점들의 가중치 중 최댓값과 최솟값의 차이가 가능한 한 커지도록 할 때, 그 최댓값을 구하시오.
위 그림에서는 회색 영역처럼 직사각형을 놓으면 포함된 점들의 가중치 최댓값과 최솟값의 차이가 7이 되며, 이보다 크게 만들 수 없다.
입력
첫째 줄에 세 정수 N, A, B가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ A ≤ 2,000,000, 1 ≤ B ≤ 2,000,000)
다음 N개의 줄에는 각 점의 행 좌표 r, 열 좌표 c, 가중치 S를 나타내는 세 정수가 주어진다. (1 ≤ r ≤ 2,000,000, 1 ≤ c ≤ 2,000,000, 1 ≤ S ≤ 2,000,000)
두 점이 같은 위치를 공유하는 경우는 없다.
출력
직사각형 안에 포함된 점들의 가중치 최댓값과 최솟값의 차이로 만들 수 있는 최댓값을 출력한다.