题目描述

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

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

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

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

6

提示

输入详细信息： 品种${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}$所以我们必须有至少两个不同的品种。