#P3535. [Usaco2014 Open]Fair Photography
[Usaco2014 Open]Fair Photography
[USACO14OPEN] Fair Photography G
题目描述
农夫约翰的 头牛各自站在一条直线围栏的不同位置上。第 头牛站在 处,品种编号为 ,共有 种品种。
约翰要给连续一段位置上的牛拍照。选定照片的左右端点后,端点及两端之间的牛都必须入镜。照片中必须有至少 个不同品种,而且每个入镜品种的牛数都相同。照片的大小是入镜牛的最右位置与最左位置之差。
请计算满足条件的照片的最大大小。如果没有合格的照片,输出 。
输入格式
第一行两个整数 。接下来 行,每行两个整数 ,分别表示一头牛的位置和品种编号。各行可按任意顺序给出。
输出格式
一行一个整数,表示合格照片的最大大小。无解时输出 。
样例 #1
9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
6
从位置 到 拍下的牛中,品种 各有两头。位置 到 之间只有品种 ,达不到 的要求。
数据范围
,,,。各 两两不同。