문 설치

현우의 사무실은 N x N 사각형 격자의 방들로 나누어져 있습니다 (2 <= N <= 15). 현재 모든 방은 문 없이 연결되어 직원들은 방 사이를 자유롭게 이동할 수 있습니다.

현우는 직원들의 프라이버시를 보호하기 위해 일부 방에 문을 설치하기로 결정했습니다. 건물 규정에 따라 각 문은 전체 사무실을 가로지르며 수평 또는 수직선이어야하며, 문은 방을 통과할 수 없습니다. 현우는 최대 K (1 <= K <= 2N - 2) 개의 문을 설치할 수 있는 예산을 가지고 있습니다.

현우의 목표는 문을 설치하여 가장 큰 직원 그룹의 크기를 최소화하는 것입니다. (문을 통과하지 않고 서로 접근 가능한 직원들은 같은 그룹으로 생각합니다). 각 방에 현재 얼마나 많은 직원들이 있는지 주어졌을 때, 문을 최적으로 설치해서 가장 큰 직원 그룹의 크기를 계산하는 것이 필요합니다.

• 첫 번째 줄 : 두 정수, N과 K
• 두 번째 줄부터 1+N 번째 줄: 사무실의 한 행에 대한 각 방에 있는 사람들을 설명하는 N개의 숫자입니다. (각 방에는 최소 0명 최대 1000명의 직원이 있습니다)

• 첫 번째 줄 : 가장 큰 직원 그룹의 가능한 최소 크기