P23455 [AtCoder] [ARC032D] AtCoder Monsters
省选
题目描述

Problem Description

AtCoder Monsters is a game where you form teams of monsters to battle.

You are at a shop that sells monsters. In this shop, $ N $ monsters are arranged in a row. Each monster $A_i\ (1\ ≦\ i\ ≦N)$ has the following two ability values:

  • The attack ability value of monster $ M_i $, denoted as $ {M_i}_{ATK} $
  • The defense ability value of monster $ M_i $, denoted as $ {M_i}_{DEF} $

You want to buy exactly $ K $ different monsters from these $ N $ monsters to form a team. However, it is known that if there are monsters with vastly different ability values in the team, the team will be unstable. Therefore, you want to form the most stable team possible.

More precisely, for any two monsters $ X $ and $ Y $ in the team, their instability $ S_{X,Y} $ is defined as:

  • $ S_{X,Y} $ = max{ $|X_{ATK}\ -\ Y_{ATK}|$, $|X_{DEF}\ -\ Y_{DEF}|$ }

The instability of the team is the maximum instability value calculated for all pairs of monsters in the team. When there is only one monster in the team, the team's instability is $ 0 $.

You want to minimize the team's instability by choosing exactly $ K $ different monsters. Additionally, you also want to find the total number of ways to choose the monsters that minimize the team's instability.

You must output the minimum achievable instability of the team and the total number of ways to achieve this minimum instability, modulo $ 1,000,000,007 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ {M_1}_{ATK} $ $ {M_1}_{DEF} $ $ {M_2}_{ATK} $ $ {M_2}_{DEF} $ : $ {M_N}_{ATK} $ $ {M_N}_{DEF} $

  • The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 100,000)$ and $K\ (1\ ≦\ K\ ≦\ N)$, representing the number of monsters in the shop and the number of monsters you want to buy, respectively.
  • The next $ N $ lines contain the ability values of the monsters in the shop. The $ i $-th line contains two integers ${M_i}_{ATK},\ {M_i}_{DEF}\ (0\ ≦\ {M_i}_{ATK},\ {M_i}_{DEF}\ ≦\ 3000)$, representing the attack and defense ability values of the $ i $-th monster.

Output Format

Output the following in one line each:

  1. The minimum achievable instability of the team.
  2. The total number of ways to achieve this minimum instability, modulo $ 1000000007 $.

Do not forget the newline at the end of the output.

Sample Input and Output

Sample Input #1

4 3
0 0
1 1
3 3
2 2

Sample Output #1

2
2

Sample Input #2

4 2
1 1000
10 100
100 10
1000 1

Sample Output #2

90
1

Sample Input #3

3 1
1 1
2 2
3 3

Sample Output #3

0
3

Sample Input #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
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
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
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
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
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
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
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
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
300

输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
4 3 0 0 1 1 3 3 2 2
样例输出
2 2