16151번 - 별자리

별의 신 디디는 자신이 만들었던 별자리를 사람들이 알아보지 못해 속상했다. 그래서 이번에는 좌표평면 상에 존재하는 별들로 알아보기 쉬운 별자리를 하나 만들려고 한다. 별자리에 속한 별들의 집합을 S라고 하자. 디디는 집합 S에 속해 있는 임의의 별을 원점으로 생각했을 때, 그 별을 제외한 S의 모든 별들이 1사분면 혹은 3사분면에 있다면, 그 별자리를 알아보기 쉽다고 생각한다. 사분면의 정의는 다음 링크를 따른다. (링크. 단, 좌표축은 사분면에 포함되지 않는다.)

올바른 예시

올바르지 않은 예시

또한, 알아보기 쉬운 별자리는 집합 S에 속해 있는 임의의 별을 원점으로 생각했을 때, 어떤 사분면에 S의 별이 존재하는 경우, 그러한 각각의 사분면에서 |X_i - X_j| + |Y_i - Y_j|가 가장 작은 별들과 아래 조건을 만족해야 한다.

|X_i - X_j| ≤ L 그리고 |Y_i - Y_j| ≤ L

(단, i는 원점으로 생각한 별, j는 그 사분면에서 |X_i - X_j| + |Y_i - Y_j|가 가장 작은 별을 의미한다.)

디디는 알아보기 쉬운 별자리 중 구성하는 별들의 밝기의 합이 가장 큰 별자리를 만들려고 한다. 디디를 도와 밝기의 합의 최댓값을 구하는 프로그램을 작성하라.

첫째 줄에 좌표평면 상에 존재하는 별의 개수 N (1 ≤ N ≤ 2 x 10⁵), 문제에서 주어진 정수 L (1 ≤ L ≤ 10⁹)이 공백으로 구분되어 주어진다.

둘째 줄부터 N개의 줄에는 각각 별의 위치 X_i, Y_i (1 ≤ X_i, Y_i ≤ 10⁹) 별의 밝기 B_i (1 ≤ B_i ≤ 10⁴)가 공백으로 구분되어 주어진다. 주어지는 입력은 모두 정수이며, 같은 위치를 가지는 별들도 입력으로 주어질 수 있음에 유의하라.

구성하는 별들의 밝기의 합이 가장 큰 알아보기 쉬운 별자리의 밝기의 합을 출력하라.