Fair Photography

FJ has $N$ cows ($1 \le N \le 100\,000$) standing along a long one-dimensional fence. Cow $i$ stands at position $x_i$ (integer in $0 \ldots 1\,000\,000\,000$) and has breed $b_i$ ($1 \ldots 8$). No two cows share a position.

FJ wants a photo of a contiguous interval of cows. Every breed that appears in the photo must appear the same number of times (for example, 27 of breed 1 and 27 of breed 3 is fine, but 9 of breed 1 and 10 of breed 3 is not). At least $K$ breeds ($K \ge 2$) must appear.

Find the maximum photo size, defined as the difference between the largest and smallest positions among cows in the photo. If no valid photo exists, output $-1$.

• Line 1: $N$ and $K$.
• Next $N$ lines: $x_i$ and $b_i$.

One integer: the maximum fair photo size, or $-1$ if none exists.

Sort by position, then check each contiguous interval for equal per-breed counts.