题目描述

在 $1025\times1025$ 的网格上有 $n$ 个老鼠窝，第 $i$ 个老鼠窝位于 $(x_i,y_i)$，有 $size_i$ 只大老鼠。

你可以布置炸弹消灭这些可怖的大老鼠，炸弹威力范围为 $d$，即炸弹布置在 $(x,y)$ 能炸死所有 $\left|x_i-x\right|+\left|y_i-y\right|\le d$ 的老鼠窝中的大老鼠。

求最多能炸死多少只大老鼠，如果有多个位置答案一样，回答 $x$ 较小的，$x$ 相同回答 $y$ 较小的。

$1\le n\le20000,1\le d\le50$

$1\le size_i\le 255,0\le x_i,y_i\le1024$

输入格式

第一行一个 $t$ 表示数据组数。

每组数据第一行一个正整数 $d$，表示炸弹威力范围；第二行一个正整数 $n$ 表示老鼠窝个数。

接下来 $n$ 行，每行三个整数 $x_i,y_i,size_i$，表示第 $i$ 个老鼠窝的坐标和老鼠数量。

输出格式

一行三个正整数 $x,y,ans$，表示炸弹在 $(x,y)$ 能炸死最多大老鼠，最多 $ans$ 只。

### 题目描述

在 $1025\times1025$ 的网格上有 $n$ 个老鼠窝，第 $i$ 个老鼠窝位于 $(x_i,y_i)$，有 $size_i$ 只大老鼠。

你可以布置炸弹消灭这些可怖的大老鼠，炸弹威力范围为 $d$，即炸弹布置在 $(x,y)$ 能炸死所有 $\left|x_i-x\right|+\left|y_i-y\right|\le d$ 的老鼠窝中的大老鼠。

求最多能炸死多少只大老鼠，**如果有多个位置答案一样，回答 $x$ 较小的，$x$ 相同回答 $y$ 较小的**。

$1\le n\le20000,1\le d\le50$

$1\le size_i\le 255,0\le x_i,y_i\le1024$

### 输入格式

第一行一个 $t$ 表示数据组数。

每组数据第一行一个正整数 $d$，表示炸弹威力范围；第二行一个正整数 $n$ 表示老鼠窝个数。

接下来 $n$ 行，每行三个整数 $x_i,y_i,size_i$，表示第 $i$ 个老鼠窝的坐标和老鼠数量。

### 输出格式

一行三个正整数 $x,y,ans$，表示炸弹在 $(x,y)$ 能炸死最多大老鼠，最多 $ans$ 只。