飞镖游戏是一个有趣的运动，你向靶子上投掷多枚飞镖，并根据它们的位置获得分数。本题中的游戏规则略有不同。

靶子可以被视为一个无限的二维平面，你已经投掷了 $N$ 枚飞镖。对于每一枚飞镖，已知其在靶子上的位置 $(X, Y)$，以及如果你算上这枚飞镖所能获得的分数（该分数可正可负，且不同飞镖即使在同一位置也可能拥有不同的分数）。

计分方式如下：在投掷完 $N$ 枚飞镖后，你需要画一个边长为 $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$ 行，每行包含 3 个由空格分隔的整数 $X, Y, S$，表示在点 $(X, Y)$ 处有一枚飞镖，如果它被计入，将为你提供 $S$ 分 ($-10^5 \le X, Y, S \le 10^5$)。

输出格式

对于每个测试用例，打印一行，包含画出正方形后能获得的最大得分。

样例

样例输入 1

2
5 8
4 5 100
3 3 4
-2 -2 -3
-1 1 2
4 -1 -101
7 10
1 1 -10
-1 1 -10
1 -1 -10
-1 -1 -10
0 1 -10
1 0 -10
2 2 -1000

样例输出 1

3
-1060

说明

下图展示了第一个样例测试用例，我们无法获取分数为 100 的点，但我们可以稍微旋转正方形，使其不再包含分数为 -101 的点。