아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

푸앙이와 레벨업

시간 제한3초메모리 제한1024 MB

요약
푸앙이가 (0,0)부터 (N-1,N-1)까지 N^2개 칸을 지나며 칸마다 K x K 범위 발도술을 한 번씩 쓸 때 경험치 R 이상을 모을 수 있는 최소 K를 구한다.
난이도

보통10점 중 6점

유형
이분 탐색, 누적 합, 행렬
정답자
아직 제출이 없습니다

문제

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

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

입력

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

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

출력

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

예제3

  1. 예제 1

    입력
    5 124
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
    예상 출력
    5

  2. 예제 2

    입력
    5 120
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
    예상 출력
    4

  3. 예제 3

    입력
    5 300
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
    예상 출력
    -1