Description

FJ 的 $N$ 头奶牛（$1 \leq N \leq 100,000$）站在一条长长的一维栅栏的不同位置。第 $i$ 头奶牛站在位置 $x_i$（范围为 0 到 1,000,000,000 的整数），其品种为 $b_i$（范围为 1 到 8 的整数）。没有两头奶牛占据相同的位置。

FJ 想为县集市拍摄一张连续区间的奶牛照片，但他希望所有的品种在照片中都能得到公平的代表。因此，他希望确保在照片中出现的任何品种数量都是相等的（例如，包含 27 头品种 1 和品种 3 的照片是可以的，包含 27 头品种 1、3 和 4 的照片也是可以的，但包含 9 头品种 1 和 10 头品种 3 的照片则不可以）。农夫约翰还希望照片中至少有 $K$（$K \geq 2$）个品种（总共 8 个品种）被代表。帮助 FJ 拍摄他的公平照片，找出满足 FJ 约束条件的最大照片大小。照片的大小是照片中奶牛的最大位置和最小位置之间的差。

如果没有满足 FJ 约束条件的照片，则输出 $-1$。

Input Format

• 第 1 行：两个用空格分隔的整数 $N$ 和 $K$。

• 第 2 行到第 $N+1$ 行：每行包含两个用空格分隔的整数，描述一头奶牛的位置 $x(i)$ 和其品种 id。

Output Format

• 第 1 行：一个整数，表示公平照片的最大大小。如果不存在这样的照片，则输出 -1。

9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3

6

Hint

输入详情：

品种 id：1 2 3 - 1 1 2 3 1 - ... - 1

位置：1 2 3 4 5 6 7 8 9 10 ... 99 100

输出详情：

从 $x = 2$ 到 $x = 8$ 的范围内有 2 头品种 1、2 和 3。范围从 $x = 9$ 到 $x = 100$ 有 2 头品种 1，但这是无效的，因为 $K = 2$，所以我们必须至少有 2 个不同的品种。

题面翻译由 ChatGPT-4o 提供。