题目描述

$\red{FJ}$的$\red{N}$头奶牛（$\red{1<=N<=100000}$）沿着一条长的一维围栏站在不同的位置。

第$\red{i}$头奶牛站在位置$\red{x_i}$（范围为$\red{0…}$$\red{100000000}$的整数）处，繁殖了$\red{b_i}$（范围为$\red{1…}$$\red{8}$的整数）。

没有两头奶牛占据同一位置。$\red{FJ}$想为县集市拍一张连续间隔的奶牛照片，但我们希望他的所有品种都能在照片中得到公平的代表。

因此，他希望确保，对于照片中出现的任何品种，每个品种的数量都是相等的（例如，一张有$\red{27}$个品种$\red{1}$和$\red{3}$的照片可以，一张有$\red{27}$个品种$\red{1}$、$\red{3}$和$\red{4}$的照片可以，但品种$\red{1}$和品种$\red{3}$的$\red{10}$的$\red{9}$个不可以）。

农民约翰还希望照片中至少有$\red{K（}$$\red{K>=2）}$个品种（总共$\red{8}$个品种）。

通过找到满足$\red{FJ}$约束的照片的最大尺寸，帮助$\red{FJ}$拍摄他的照片。照片的大小是照片中奶牛的最大和最小位置之间的差异。

如果没有满足$\red{FJ}$约束的照片，则输出$\red{-1}$。

输入格式

第$\red{1}$行：由空格分隔的$\red{N}$和$\red{K}$

第$\red{2...N+1}$行：每行包含一头奶牛的描述，分为两头由空格分隔的整数；$\red{x（}$$\red{i）}$及其品种$\red{id}$。

输出格式

第$\red{1}$行：一个整数，表示展会的最大规模照片如果不存在此类照片，则输出$\red{-1}$。

样例

输入样例

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

输出样例

6

提示

输入详细信息： 品种$\red{ID:1 2 3-1 1 2 3 1-…}$$\red{-1.}$位置：$\red{1 2 3 4 5 6 7 8 9 10...}$$\red{99 100}$

输出详细信息：

从$\red{x=2}$到$\red{x=8}$的范围内有$\red{2}$个品种$\red{1}$、$\red{2}$和$\red{3}$。

范围从$\red{x=9}$到$\red{x=100}$有$\red{2}$个品种$\red{1，}$但这是无效的，因为$\red{K=2}$所以我们必须有至少两个不同的品种。