AT_arc032_4 [ARC032D] アットコーダーモンスターズ

アットコーダーモンスターズ是一款组建怪兽队伍进行战斗的游戏。 你现在在一家出售怪兽的商店里。在这家商店中，有 $N$ 只怪兽排成一行。每只怪兽 $A_i\ (1\leq i\leq N)$ 都有如下两项能力值： - 怪兽 $M_i$ 的攻击能力值 ${M_i}_{ATK}$ - 怪兽 $M_i$ 的防御能力值 ${M_i}_{DEF}$ 现在，你打算从这 $N$ 只怪兽中选出恰好 $K$ 只不同的怪兽购买，并用它们组建队伍。然而，如果队伍中某项能力值相差太大的怪兽同时存在，队伍就会变得不稳定，因此你希望组建一个尽可能稳定的队伍。 更严格地说，对于队伍中任意两只怪兽 $X$ 和 $Y$，定义它们之间的不稳定度 $S_{X,Y}$ 为： - $S_{X,Y} = \max\{ |X_{ATK} - Y_{ATK}|, |X_{DEF} - Y_{DEF}| \}$ 队伍的不稳定度为队伍中所有怪兽两两之间不稳定度的最大值。当队伍中只有一只怪兽时，队伍的不稳定度为 $0$。 你希望购买 $K$ 只怪兽，使得组建的队伍不稳定度最小。同时，你还想知道能够达到最小不稳定度的选法有多少种。 你需要输出能够达到的最小队伍不稳定度，以及达到该不稳定度的选法数对 $1,000,000,007$ 取模的结果。

输入通过标准输入给出，格式如下： > $N$ $K$ > ${M_1}_{ATK}$ ${M_1}_{DEF}$ > ${M_2}_{ATK}$ ${M_2}_{DEF}$ > $\vdots$ > ${M_N}_{ATK}$ ${M_N}_{DEF}$ - 第 $1$ 行包含两个整数 $N\ (1\leq N\leq 100,000)$ 和 $K\ (1\leq K\leq N)$，分别表示商店中怪兽的数量和要购买的怪兽数量。 - 接下来的 $N$ 行，每行包含两个整数，分别表示第 $i$ 只怪兽的攻击能力值和防御能力值 $({M_i}_{ATK},\ {M_i}_{DEF})\ (0\leq {M_i}_{ATK},\ {M_i}_{DEF}\leq 3000)$。

第 $1$ 行输出能够达到的最小队伍不稳定度。 第 $2$ 行输出能够达到最小不稳定度的选法数对 $1000000007$ 取模的结果。 注意末尾需要换行。

### 部分分 本题设置了部分分。 - 有 $10$ 分的测试点满足 $1\leq N\leq 20$。 ### 样例解释 1 怪兽排列如下，选择 $3$ 只怪兽时，最小不稳定度为 $2$。同时，选法有 $2$ 种。  由 ChatGPT 4.1 翻译