Fair Photography

Time limit1sMemory limit128 MB

Summary

After sorting cows by position, find the widest contiguous group containing at least K breeds with each present breed appearing equally often.

Level: Medium7 of 10
Topics: Prefix sum, Hash map
Solved: No attempts yet

Problem

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$ .

Input

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

Output

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

Hint

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

Examples6

Example 1

Input

Expected output

Example 2
Input
```
3 2
1 1
4 2
7 1
```
Expected output
```
6
```
Example 3
Input
```
4 2
1 1
2 1
3 2
4 2
```
Expected output
```
3
```

Example 4

Input

Expected output

Example 5

Input

Expected output

Example 6

Input

Expected output