题目内容

在一个无限大的二维平面上，分布着 $n$ 个信号中继站。第 $i$ 个中继站的坐标为 $(x_i, y_i)$，它会在时刻 $s_i$ 自动激活。激活时，该中继站会向所有与它曼哈顿距离不超过 $r_i$ 的其他中继站发送激活信号，这些中继站会被立刻激活（无论它们自身的 $s_i$ 是否到达），并继续引发新的激活。若两个坐标 $(x_1,y_1)$ 与 $(x_2,y_2)$ 的曼哈顿距离定义为 $|x_1 - x_2| + |y_1 - y_2|$。请你计算，最早在什么时刻，平面上至少有 $m$ 个中继站处于激活状态。

数据范围：单个测试数据中 $n$ 不超过 $2000$，$1 \le m \le n$；所有测试数据的 $n$ 之和不超过 $3000$。坐标的绝对值不超过 $10^9$，$0 \le s_i \le 10^9$，$0 \le r_i \le 2 imes 10^9$。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试数据组数。每组数据格式如下： 第一行输入两个整数 $n$ 和 $m$，表示中继站总数和至少需要激活的中继站数量。 接下来 $n$ 行，第 $i$ 行包含四个整数 $x_i$、$y_i$、$s_i$、$r_i$，依次描述第 $i$ 个中继站的横坐标、纵坐标、自动激活时刻和激活影响半径。