FJ의 농장은 N*N 격자의 목초지(2 <= N <= 15)로 나뉘어져 있다. 농장 바깥에 울타리가 쳐져 있지만, 안에 있는 소들은 한 목초지에서 다른 목초지로 마음껏 이동할 수 있다.

FJ는 소들을 분리시키기 위해서 울타리를 치기로 했다. 법 때문에, 울타리는 수평 또는 수직방향으로 농장 전체에 걸쳐서 쳐야 하고, 목초지 위는 가로지를 수 없다. 그런데 FJ는 돈이 많지 않아서, K개(1 <= K <= 2N – 2)의 울타리를 칠 돈 밖에 없다.

FJ는 같은 그룹에 있는 소들의 수의 최댓값이 최소가 되도록 울타리를 치고 싶다.(울타리를 넘지 않고 목초지 사이를 이동할 수 있으면 같은 그룹에 있다고 한다) 각 목초지에 있는 소들의 수가 입력으로 주어질 때, 같은 그룹에 있는 소들의 수의 최댓값이 최소가 되도록 구하시오.

Line 1 : 두 정수 N, K가 입력으로 주어진다.

Line 2~N+1 : 한 줄에 N개의 수가 주어지는데, 각 숫자는 그 위치에 해당하는 목초지의 정보를 나타낸다.(각 목초지에 살고 있는 소들의 수는 0과 1,000 사이이다.)

Line 1 : 같은 그룹에 있는 소들의 수의 최댓값이 최소가 되도록 구하시오.

USACO 2013 Feb Gold