问题描述

名为 AtCoder Monsters 的游戏是一款组建怪兽队伍进行战斗的游戏。

你正在一家卖怪兽的商店里。在这家商店里，有 $N$ 只怪兽排成一行。每只怪兽 $A_i (1 \leq i \leq N)$ 都有以下两个能力值：

• 表示怪兽 $M_i$ 攻击能力的值 $M_{i_{ATK}}$
• 表示怪兽 $M_i$ 防御能力的值 $M_{i_{DEF}}$

现在，你想购买并组建一个由 $N$ 只不同的怪兽组成的团队。然而，由于已知如果某个能力值相差太大的怪兽之间放在一起，团队就不稳定，所以你想尽可能地组建一个稳定的团队。

更准确地说，我们定义团队的不稳定度 $S_{X,Y}$ ，对于团队中的任意两只怪兽 $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}}$ : $M_{N_{ATK}}$ $M_{N_{DEF}}$

• 第一行包含两个整数 $N$ 和 $K$ ，分别表示商店中排列的怪兽数量和想要购买的怪兽数量 ($1 \leq N \leq 100,000$，$1 \leq K \leq N$)。
• 接下来的 $N$ 行描述商店中怪兽的能力值信息。其中第 $i$ 行包含两个整数 $M_{i_{ATK}}, M_{i_{DEF}} (0 \leq M_{i_{ATK}}, M_{i_{DEF}} \leq 3000)$，以空格分隔。

---

部分得分

本问题有部分得分。

• 对于10分的测试用例，保证 $1 \leq N \leq 20$ 。

---

输出

在第一行上输出可以达到的团队的最小不稳定度。

在第二行上输出选择怪兽以最小化团队的不稳定度的方法总数对 $1000000007$ 取模后的余数。

请确保输出末尾有换行符。

---

示例输入1

4 3
0 0
1 1
3 3
2 2

示例输出1

2
2

怪兽排列如下图所示，选择3只时，最小不稳定度为2。同时，有2种选择方式。

---

示例输入2

4 2
1 1000
10 100
100 10
1000 1

示例输出2

90
1

---

示例输入3

3 1
1 1
2 2
3 3

示例输出3

0
3

---

示例输入4

40 18
0 0
0 0
0 0
0 0
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000
3000 3000

示例输出4

0
75135237

---