25599번 - 푸앙이와 레벨업

모험하던 푸앙이는 정체불명의 던전에 도착했다. 던전은 $N \times N$ 정사각형 모양이다. 던전의 모든 칸엔 몬스터가 배치되어있다. $A_{ij}$는 $(i,\,j)$에 위치한 몬스터가 주는 경험치를 의미한다. 많은 몬스터를 죽여 레벨업을 위한 경험치인 $R$ 이상을 모으고 싶은 푸앙이는 던전의 시작점인 $(0,\,0)$부터 끝점인 $(N - 1,\,N - 1)$까지 $N^2$개의 칸을 모두 걸어 다닌다. 던전의 한 칸당 한 번, 푸앙이는 발도술을 사용할 수 있다. 발도술은 푸앙이로부터 $x$, $y$축이 증가하는 방향으로 $K \times K$정사각형 영역만큼의 범위를 가진다. 발도술을 사용하면, 던전 내부와 발도술 영역에 있는 몬스터 중 $1$마리를 사냥하여 경험치를 얻을 수 있다. 던전의 특수성으로, 사냥 당한 몬스터는 즉시 리스폰된다. 푸앙이는 되도록 적은 힘으로 발도술을 사용하면서 레벨업을 하고 싶다. 푸앙이가 레벨업을 할 수 있는 발도술 영역 $K$의 최솟값을 출력하시오.

다음은 $K = 3$ 일 때 푸앙이가 $(1,\,1)$ 지점에서 시전한 발도술 영역이다.

첫 번째 줄에 $N$ $(3 \leq N \leq 1\,000)$, 정수 $R$ $(1 \leq R \leq 10^{12})$이 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에는 던전 정보가 주어진다. 던전 정보는 공백을 사이로 두고 던전 각 칸에 위치한 몬스터가 주는 경험치가 정숫값으로 주어진다. $(0 \leq A_{ij} \leq 10\,000\,000)$

푸앙이가 레벨업을 할 수 있는 발도술 영역 $K$의 최솟값을 출력하시오. 만약 푸앙이가 레벨업 하는 것이 불가능하다면 $-1$을 출력하시오.