게으른 소

더운 여름날, 소 베시는 몹시 게으르다. 베시는 들판에서 자신의 위치를 정해, 짧은 거리 안에서 먹을 수 있는 풀이 최대한 많은 지점을 고른다.

베시의 들판에는 풀 패치가 $N$개 있다 ($1 \le N \le 100\,000$). 각 패치 $i$에는 $g_i$단위의 풀이 있고 ($1 \le g_i \le 10\,000$), 서로 다른 좌표 $(x_i, y_i)$에 놓여 있다 ($0 \le x_i, y_i \le 1\,000\,000$). 베시는 들판의 한 점을 시작 위치로 정한다. 이 점은 풀 패치 위일 수도 있고, 정수 좌표가 아닐 수도 있다. 시작 위치에서 $K$보 이하(맨해튼 거리) 안에 있는 풀의 총량을 최대화하는 위치를 찾아야 한다 ($1 \le K \le 2\,000\,000$).

베시가 한 보를 걸면 북, 남, 동, 서로 정확히 1단위 이동한다. 예를 들어 $(0,0)$에서 $(3,2)$까지는 5보가 필요하다. 보의 길이를 나눠 쓸 수 있다. 북쪽으로 0.5, 동쪽으로 0.5 이동하는 것도 한 보로 본다.

• 첫 줄: 정수 $N$, $K$
• 다음 $N$줄: 각 줄에 $g_i$, $x_i$, $y_i$ (풀의 양과 좌표)

한 줄에, 시작 위치를 최적으로 고를 때 $K$보 이내에서 먹을 수 있는 풀의 최대 총량을 출력한다.

좌표를 $(u,v)=(x+y, x-y)$로 바꾸면 맨해튼 거리 제한이 $|u-u_0|\le K$와 $|v-v_0|\le K$를 동시에 만족하는 직사각형 영역이 된다. $u$로 정렬한 뒤 폭 $2K$ 이내의 구간을 슬라이딩 윈도우로 훑고, 구간 안에서 $v$에 대해 같은 방식으로 합을 계산하면 된다.