题目内容

小塔来到了一个无限大的二维平面上，平面中有$n$个地雷，其中第$i$个地雷的坐标为($x_i,y_i$),且第$t_i$秒它就会爆炸，它的爆炸冲击会引爆和它曼哈顿距离在$k_i$以内的所有其它地雷。小塔现在想知道，至少需要多长时间，才能使得至少$m$个地雷爆炸。 ($x_1,y_1$) 和($x_2, y_2$)的曼哈顿距离定义为:$dist =|x1 - x2|+|y1-y2|$。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤100$)代表数据组数，每组测试数据描述如下: 第一行输入两个整数$n,m$($1≤m≤n≤2000$)，表示平面中地雷的个数和至少需要$m$个地雷爆炸。 此后$n$行,第$i$行输入四个整数 $x_i,Y_i,t_i,k_i$($-10^9≤x,y≤10^9,0≤t_i≤10^9,0≤k_i≤2x10^9$),描述第$i$个地雷。 除此之外，保证所有的$n$之和不超过$3000$。

输出描述

在一行上输出一个整数，代表最少的等待时间

样例1

输入

1
3 3
0 0 0 1
1 0 1 1
2 2 3 10

输出

3