Fair Photo

Farmer John has (N) cows ((1 \le N \le 100000)) standing at various positions along a one‐dimensional fence. The (i)th cow is located at position (x_i) (an integer in the range (0 \ldots 10^9)) and has breed (b_i) (an integer in the range (1 \ldots 8)). No two cows share the same position.

FJ wants to take a photo of a contiguous group of cows for the county fair. In this photo, for every breed that appears, the number of cows of that breed must be identical. For example, a photo with 27 cows each of breeds 1 and 3 is valid, as is a photo with 27 cows each of breeds 1, 3, and 4. However, a photo with 9 cows of breed 1 and 10 cows of breed 3 is not valid. In addition, at least (K) (with (K \ge 2)) different breeds must be represented in the photo.

The size of a photo is defined as the difference between the maximum and minimum position of the cows in the photo. Help FJ determine the maximum possible photo size that meets his constraints. If no such photo exists, output (-1) instead.

(\textbf{Hint:}) One way to check if an interval is fair is to note that all non-zero breed counts must be equal. By taking the prefix counts sorted by position and considering the differences (\text{diff}_j = (c_2-c_1, c_3-c_1, \ldots, c_8-c_1)), an interval is balanced if the difference between two prefix states is a zero vector. Remember to verify that the interval contains at least (K) distinct (nonzero) breeds.

inputFormat

The first line contains two integers (N) and (K). Each of the next (N) lines contains two integers (x_i) and (b_i), representing the position and breed of the (i)th cow. The cows may be given in arbitrary order.

outputFormat

Output a single integer: the maximum size of a fair photo satisfying FJ's constraints, or (-1) if no valid photo exists.

sample

5 2
1 1
7 2
4 1
10 3
3 2

6