Chụp Ảnh Công Bằng (Gold)

Nông dân có $N$ con bò đứng trên một hàng rào, mỗi con thuộc một trong 8 giống (đánh số từ 1 đến 8). Mỗi con bò có một vị trí nguyên trên hàng rào (không có hai con cùng vị trí).

Nông dân muốn chụp một bức ảnh bao gồm một đoạn liên tiếp các con bò (theo vị trí) sao cho:

• Có ít nhất $K$ giống bò xuất hiện trong ảnh ($K\ge 2$).
• Tất cả các giống xuất hiện trong ảnh phải có số lượng bằng nhau.

Kích thước bức ảnh được tính bằng hiệu giữa vị trí lớn nhất và nhỏ nhất của các con bò trong ảnh. Hãy tìm kích thước lớn nhất có thể, hoặc in $-1$ nếu không tồn tại bức ảnh hợp lệ.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $K$.

• $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$ và $b_i$ — vị trí và giống của con bò thứ $i$.

Dữ liệu ra

Một số nguyên duy nhất — kích thước lớn nhất của bức ảnh hợp lệ, hoặc $-1$ nếu không tồn tại.

Ràng buộc

• $1\le N\le 100000$
• $2\le K\le 8$
• $0\le x_i\le {10}^9$
• $1\le b_i\le 8$
• Không có hai con bò cùng vị trí

Ví dụ