题目描述

直线上有n个点，每个点有个坐标xi和类型bi，点互不重合，给定一个数k。要求你选择一个区间[L,R]，每类数在[

L,R]里，要么出现0次要么出现次数均相等，且出现过的品种数至少为k一个区间的长度是最右边的输入点减最左边

的输入点，如果没有点则是0要你最大化区间长度

输入格式

第一行输入n,k

接下来n行，每行两个数xi,bi

n ≤ 100000, 1 ≤ k, bi ≤ 8, xi ≤ 10^9

输出格式

输出一个数表示答案

样例

样例输入

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

样例输出

6