귀여운 작은 나비

마법 세계의 숲에는 마법 생물로 가득한 정원이 있다. 정원에는 아름다울 뿐만 아니라 나비에게 에너지를 공급하는 꽃이 많이 있다.

정원을 X축이 지면을 나타내고 Y축이 고도를 나타내는 2D 평면이라고 생각하자. X축 위의 음이 아닌 모든 정수 좌표에는 높이가 무한한 식물이 있다. 정원에는 $\mathbf{N}$개의 꽃이 있으며, $i$번째 꽃은 점 ($\mathbf{X_i}$, $\mathbf{Y_i}$)에 있고 에너지 값이 $\mathbf{C_i}$인 꿀을 가지고 있다.

우리의 귀여운 작은 나비는 강해지기 위해 가능한 한 많은 에너지를 원한다. 꽃과 같은 위치로 이동하면 나비는 그 꽃의 꿀을 섭취하여 꽃의 에너지 값만큼 에너지를 얻을 수 있다. 각 꽃의 꿀은 한 번만 섭취할 수 있다.

나비는 처음에 점 $(0, 10^{18})$에 있으며, 에너지는 $0$단위이고 오른쪽을 향하고 있다. 어느 지점에서든 나비는 다음 행동을 할 수 있다.

• 현재 고도가 양수인 경우에만 고도가 더 낮은 곳으로, 즉 $(x, y)$에서 $(x, y-1)$로 이동한다($y > 0$).

• 오른쪽을 향하고 있다면 X축의 양의 방향으로, 즉 $(x, y)$에서 $(x+1, y)$로 이동한다.

• 왼쪽을 향하고 있다면 X축의 음의 방향으로, 즉 $(x, y)$에서 $(x-1, y)$로 이동한다.

• 바라보는 방향을 바꾼다(왼쪽에서 오른쪽으로 또는 그 반대로). 이 행동은 에너지 $\mathbf{E}$단위를 소모한다.

우리의 나비는 게으르고 이동 중에 위쪽으로 움직이는 것을 싫어한다. 따라서 이 문제에서는 위쪽으로 이동할 수 없다고 가정한다. 또한 어느 시점에서든 에너지는 음수일 수 있다. 음의 에너지는 나비가 꽃에서 얻은 에너지보다 더 많은 에너지를 소모했다는 뜻이다.

우리의 귀여운 나비가 달성할 수 있는 최대 에너지를 구하라.

제한

메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $0 \le \mathbf{E} \le 10^9$. 모든 $i$에 대해 $1 \le \mathbf{C_i} \le 10^9$. 모든 꽃은 서로 다른 점에 있다.

테스트 세트 1

시간 제한: 20초. $1 \le \mathbf{N} \le 6$. 모든 $i$에 대해 $0 \le \mathbf{X_i} \le 500$. 모든 $i$에 대해 $0 \le \mathbf{Y_i} \le 500$.

테스트 세트 2

시간 제한: 40초. $1 \le \mathbf{N} \le 10^3$. 모든 $i$에 대해 $0 \le \mathbf{X_i} \le 500$. 모든 $i$에 대해 $0 \le \mathbf{Y_i} \le 500$.

테스트 세트 3

시간 제한: 60초. 모든 $i$에 대해 $0 \le \mathbf{X_i} \le 10^5$. 모든 $i$에 대해 $0 \le \mathbf{Y_i} \le 10^9$. 최대 10개의 케이스에 대해: $1 \le \mathbf{N} \le 10^5$. 나머지 케이스에 대해: $1 \le \mathbf{N} \le 10^4$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 정수 $\mathbf{N}$와 $\mathbf{E}$가 주어진다. 이들은 각각 꽃의 수와 방향을 한 번 바꾸는 데 필요한 에너지이다. 다음 $\mathbf{N}$개의 줄은 꽃을 설명한다. $i$번째 줄에는 세 정수 $\mathbf{X_i}$, $\mathbf{Y_i}$, $\mathbf{C_i}$이 주어진다. 이들은 각각 $i$번째 꽃의 위치와 에너지 값이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이고(1부터 시작), $y$는 우리의 귀여운 나비가 달성할 수 있는 전체 에너지의 최댓값이다.

예제 테스트 케이스 #1에는 $\mathbf{N} = 4$개의 꽃이 있고 $\mathbf{E} = 10$이다. 전체 에너지를 최대화하기 위해 나비는 다음과 같이 이동할 수 있다.

• 두 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 2단위이다

• 오른쪽으로 이동하여 네 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 4단위이다

• 아래로 이동하여 세 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 6단위이다

따라서 나비가 이 방법으로 얻은 총에너지는 $6$단위이다.

예제 테스트 케이스 #2에는 $\mathbf{N} = 6$개의 꽃이 있고 $\mathbf{E} = 5$이다. 전체 에너지를 최대화하기 위해 나비는 다음과 같이 이동할 수 있다.

• 세 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 5단위이다

• 오른쪽과 아래쪽으로 이동하여 네 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 7단위이다

• 오른쪽과 아래쪽으로 이동하여 다섯 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 8단위이다

• 방향을 왼쪽으로 바꾼다. 이제 총에너지는 3단위이다

• 왼쪽으로 이동하여 여섯 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 13단위이다

• 왼쪽과 아래쪽으로 이동하여 첫 번째 꽃에서 에너지를 얻는다. 이제 총에너지는 17단위이다

따라서 나비가 이 방법으로 얻은 총에너지는 $17$단위이다.