다트 게임

다트는 재미있는 게임이다. 이 문제의 게임은 조금 다르다.

보드는 무한한 2차원 평면으로 볼 수 있으며, 다트 $N$개를 이미 던졌다. 각 다트는 좌표 $(X, Y)$에 있고 점수 $S$를 가진다. 같은 위치에 여러 다트가 있을 수 있고, 위치가 같아도 점수는 다를 수 있다. 점수는 음수일 수도 있다.

다트를 모두 던진 뒤, 평면 위에 한 변의 길이가 $L$인 정사각형을 그려야 한다. 정사각형의 중심은 반드시 $(0, 0)$이어야 한다. 정사각형은 원하는 방향으로 회전시킬 수 있지만, 회전은 다트를 고려하기 전에 한 번만 한다.

정사각형 안에 있거나 경계 위에 있는 다트의 점수를 모두 얻는다. 다트의 위치와 점수, 그리고 $L$이 주어졌을 때 얻을 수 있는 점수의 최댓값을 구하라. 정사각형이 다트를 하나도 포함하지 않아도 된다.

테스트 케이스는 하나 이상 주어진다. 첫 줄에 테스트 케이스 수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫 줄에는 다트 수 $N$ ($1 \le N \le 10^5$)과 정사각형의 한 변 길이 $L$ ($1 \le L \le 10^5$)이 공백으로 구분되어 주어진다. 이어서 $N$개의 줄에 정수 $X$, $Y$, $S$가 공백으로 구분되어 주어진다. 이는 좌표 $(X, Y)$에 있는 다트가 점수 $S$를 준다는 뜻이다. 모든 값은 $-10^5 \le X, Y, S \le 10^5$을 만족한다.

각 테스트 케이스마다 정사각형을 그려 얻을 수 있는 최대 점수를 한 줄에 출력한다.

이 그림은 첫 번째 테스트 케이스를 나타낸다. 점수 100을 주는 점을 포함할 방법은 없지만, 정사각형을 조금 회전하면 점수 -101을 주는 점은 포함하지 않게 할 수 있다.