N (1 <= N <= 100,000) коров Фермера Джона стоят в различных позициях вдоль длинной изгороди. I-ая корова находится на позиции xi (целое число в интервале 0...1,000,000,000) и имеет породу bi (целое число в интервале 1..8). Никакие две коровы не занимают одну и ту же позицию.
ФД хочет сделать фотографию непрерывного интервала коров, но так чтобы все породы коровы были представлены одинаковым количеством коров. Например, фото из 27 коров породы 1 и 27 коров породы 3 – подходит, фото из 27 коров породы 1 и 27 коров породы 3 – подходит и 27 коров породы 4 тоже подходит, а 9 породы 1 и 10 породы 3 не подходит. ФД также хочет чтобs по крайнеq мере K (K>=2) пород из 8 имеющихся были представлены на фото. Помогите ФД определить фот максимального размера, которое удовлетворяет требованиям ФД. Размер фото – это разница между максимальной и минимальной позициями коров на фото.
Если не существует фото, удовлетворяющего всем ограничениям, выведите -1.
PROBLEM NAME: fairphoto
Формат ввода:
* Строка 1: N и K разделённые одним пробелом
* Строки 2..N+1: Каждая строка содержит описание одной коровы двумя целыми числами, разделёнными одним пробелом: xi и ID-породы
Примечание
ID пород: 1 2 3 - 1 1 2 3 1 - ... - 1 Местоположения: 1 2 3 4 5 6 7 8 9 10 ... 99 100
Формат вывода:
* Строка 1: Одно целое число, указывающее максимальный размер подходящего фото. Если таких фото нет, выведите -1.
Примечание
В интервале от x = 2 до x = 8 имеется по 2 коровы каждой из пород 1, 2,3. В интервале от 9 до 100 есть 2 коровы породы 1, но поскольку K=2, этот интервал не подходит.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
9 2
1 1
5 1
6 1
9 1
100 1
2 2
7 2
3 3
8 3
|
6
|