← 返回题目列表

AtCoder · arc032_4

D. 在 Coder Monsters

中文机器翻译题面 查看原题

問題文

Atcoder Monsters 是一款你可以组建怪物团队并进行战斗的游戏。

你在一家出售怪物的商店里。 在这家店里,N 怪物水平排列。还有每个怪物 A_i (1 ≦ i ≦N) 如下所示。 2 有两个能力值。

  • 怪物 代表 M_i 能力的值 {M_i}_{ATK}
  • 怪物 代表 M_i 代表Nobougyo能力的值 {M_i}_{DEF}

现在,N 与怪物不同 K 我已经选择并购买了怪物,并正在尝试与它们组队。 然而,我们知道,如果存在具有不同能力值的怪物,团队将不稳定,因此我们希望创建一个尽可能稳定的团队。

更准确地说,包含在团队中 2 怪物 X 和 Y 的不稳定性 S_{X,Y} ,

  • S_{X,Y} = 最大值{ |X_{ATK} - Y_{ATK}|, |X_{DEF} - Y_{DEF}| }

当定义时,团队的不稳定性是为团队中包含的所有怪物对计算的不稳定性的最大值。 队伍中包含的怪物 1 当有 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}
  • 1 行表示商店中排列的怪物数量以及您想要购买的怪物数量。 2 整数 N (1 ≦ N ≦ 100,000) 和 K (1 ≦ K ≦ N) 用空格分隔。
  • 2 从行 N 行提供了有关商店中排列的怪物的能力值的信息。这几天之一 i 行中,i 代表怪物的能力值 2 整数 {M_i}_{ATK}, {M_i}_{DEF} (0 ≦ {M_i}_{ATK}, {M_i}_{DEF} ≦ 3000) 用空格分隔。

部分点

针对此问题设置了部分分数。 如果所有满足

  • 10 在点的测试用例中,1≦N≦20 符合。

出力

1 行中,输出可以达到的团队不稳定性的最小值。

2 行显示了选择怪物以最大限度地减少团队不稳定的方法总数。 打印除以 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