矩形框选

Problem Description

在平面上有 $n$ 个点，第 $i$ 个点位于（$x_i+0.5,y_i+0.5$）（$x_i,y_i$ 均为整数），其价值为 $v_i$。请挑选四个整数 $a,b,c,d$（$a < b$, $c < d$），使得以 （$a,c$）、（$b,c$）、（$a,d$）、（$b,d$）为四个顶点的矩形内覆盖的所有点的价值之和最大，且矩形的面积（$b-a$）×（$d-c$）不超过 $k$。

Input

第一行包含一个正整数 $T$（$1\leq T\leq 100$），表示测试数据的组数。 每组数据第一行包含两个正整数 $n,k$（$1\leq n,k\leq 10\,000$），分别表示点数以及矩形的面积上限。 接下来 $n$ 行，每行三个正整数 $x_i,y_i,v_i$（$1\leq x_i,y_i\leq n$, $1\leq v_i\leq 10\,000$），分别描述每个点的坐标和价值。请注意，一个位置可能存在多个点。 输入数据保证 $\sum n\leq 100\,000$。

Output

对于每组数据输出一行一个整数，即矩形内覆盖的所有点的价值之和的最大可能值。

Sample Input

2
5 4
1 2 5
2 1 8
4 4 1
4 5 2
5 5 3
2 1
1 1 1
1 1 1

Sample Output

13
2

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（7）