\(N\) con bò của Farmer John (\(1 \le N \le 100\,000\)) đang đứng tại nhiều vị trí khác nhau dọc theo một hàng rào dài một chiều. Con bò thứ \(i\) đứng tại vị trí \(x_i\) (một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\)) và thuộc giống \(b_i\) (một số nguyên trong đoạn từ \(1\) đến \(8\)). Không có hai con bò nào đứng cùng một vị trí.

Farmer John muốn chụp ảnh một đoạn liên tiếp gồm các con bò để mang đến hội chợ hạt, nhưng ông muốn tất cả các giống xuất hiện trong ảnh được đại diện một cách công bằng. Vì vậy, với những giống có mặt trong ảnh, ông muốn số bò của mỗi giống đều bằng nhau. Chẳng hạn, một bức ảnh có \(27\) con thuộc mỗi giống \(1\) và \(3\) là hợp lệ; một bức ảnh có \(27\) con thuộc mỗi giống \(1\), \(3\) và \(4\) cũng hợp lệ; nhưng một bức ảnh có \(9\) con giống \(1\) và \(10\) con giống \(3\) thì không hợp lệ. Farmer John còn muốn trong ảnh có ít nhất \(K\) giống (\(K \ge 2\)) trong tổng số \(8\) giống.

Hãy giúp Farmer John chụp một bức ảnh công bằng bằng cách tìm kích thước lớn nhất của một bức ảnh thỏa mãn các điều kiện trên. Kích thước của bức ảnh là hiệu giữa vị trí lớn nhất và vị trí nhỏ nhất của các con bò trong ảnh. Nếu không có bức ảnh nào thỏa mãn các điều kiện, hãy in ra \(-1\).

Dữ liệu vào

• Dòng đầu tiên chứa \(N\) và \(K\), cách nhau bởi một dấu cách.
• \(N\) dòng tiếp theo, mỗi dòng mô tả một con bò bằng hai số nguyên cách nhau bởi một dấu cách: vị trí \(x(i)\) và chỉ số giống của nó.

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(K \ge 2\) và có tổng cộng \(8\) giống.
• \(0 \le x_i \le 1\,000\,000\,000\).
• \(1 \le b_i \le 8\).
• Không có hai con bò nào đứng cùng một vị trí.

Dữ liệu ra

• In ra một số nguyên duy nhất là kích thước lớn nhất của một bức ảnh công bằng. Nếu không có bức ảnh như vậy, in ra \(-1\).

Ví dụ

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

6

Chỉ số giống: 1 2 3 - 1 1 2 3 1  - ...  -   1
Vị trí:       1 2 3 4 5 6 7 8 9 10 ... 99 100

Nguồn

USACO 2014 US Open, Gold — Problem 1: Fair Photography

Tác giả đề: Brian Dean, 2014.