농장 분할

농부 John의 농장은 $N \times N$ 크기의 정사각형 목초지 격자로 이루어져 있습니다 ($2 \le N \le 15$). 지금은 농장 바깥쪽에만 울타리가 있어서 소들이 목초지 사이를 자유롭게 오갈 수 있습니다.

농부 John은 소들을 서로 분리하기 위해 울타리를 세우기로 했습니다. 규정상 각 울타리는 농장 전체를 가로지르는 가로선 또는 세로선이어야 하며, 목초지 내부를 통과할 수는 없습니다. 즉 모든 울타리는 인접한 두 행 사이 또는 인접한 두 열 사이에 놓입니다. 농부 John은 최대 $K$개의 울타리만 세울 수 있습니다 ($1 \le K \le 2N - 2$).

한 그룹의 크기는 그 그룹에 속한 목초지들의 소 마릿수 합입니다. 두 소는 울타리를 넘지 않고 서로에게 도달할 수 있으면 같은 그룹에 속합니다. 농부 John은 울타리를 최적으로 세워서 만들어지는 가장 큰 그룹의 크기를 최소화하려고 합니다. 각 목초지의 현재 소 마릿수가 주어질 때, 울타리를 최적으로 세웠을 때 가장 큰 그룹의 소 마릿수를 구하세요.

• 첫째 줄: 두 정수 $N$과 $K$가 주어집니다.
• 둘째 줄부터 $N$개의 줄: 각 줄에 $N$개의 정수가 주어지며, 농장의 한 행에 있는 각 목초지의 소 마릿수를 나타냅니다. 각 목초지의 소 마릿수는 $0$ 이상 $1000$ 이하입니다.

• 첫째 줄: 울타리를 최적으로 세웠을 때 가장 큰 소 그룹이 가질 수 있는 최소 크기(소 마릿수)를 출력합니다.

예시 설명

2번째 열과 3번째 열 사이, 그리고 2번째 행과 3번째 행 사이에 울타리를 세우면 각각 소 $4$마리씩인 $4$개의 그룹이 만들어집니다. 따라서 가장 큰 그룹의 크기는 $4$입니다.