FJ's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (an integer in the range 1..8). No two cows occupy the same position.

FJ wants to take a photo of a contiguous interval of cows, ensuring that, for whatever breeds are present in the photo, there is an equal number of each breed. Farmer John also wants at least K (K >= 2) breeds (out of the 8 total) to be represented in the photo. Help FJ by finding the maximum size of a photo that satisfies his constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo.

If there are no photos satisfying FJ's constraints, output -1 instead.

Line 1: N and K separated by a space.

Lines 2..N+1: Each line contains a description of a cow as two integers: x(i) and its breed id.

A single integer indicating the maximum size of a fair photo. If no such photo exists, output -1.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > US Open > Gold