부지 구매

시간 제한1초메모리 제한128 MB

요약

가격이 음이 아닌 정수인 n×n 격자가 주어질 때, 합이 k 이상 2k 이하인 직사각형 영역이 존재하는지 판정한다.

난이도: 어려움10점 중 8점
유형: 누적 합, 그리디, 이분 탐색, 구현
정답자: 아직 제출이 없습니다

문제

Byteasar는 산업용 부지를 사려고 한다. 그의 재산은 정확히 $k$ 바이탈러이고, 그 금액을 부지 구매에 쓰고 싶어 한다. 하지만 가격이 정확히 $k$ 바이탈러인 부지를 찾기는 어렵다. 그래서 그는 조금 더 비싼 부지도 살 생각이다. 은행이 최대 $k$ 바이탈러까지 대출해 주므로, 그는 최대 $2k$ 바이탈러까지 쓸 수 있고, 최소 $k$ 바이탈러 이상은 쓰고 싶어 한다.

부지를 찾는 지역은 한 변의 길이가 $n$ 미터인 정사각형이며, $n \times n$ 개의 단위 정사각형으로 나뉜다. 각 단위 정사각형에는 가격이 정해져 있다. 필지는 여러 개의 온전한 단위 정사각형으로 이루어진 직사각형이고, 그 가격은 포함된 단위 정사각형들의 가격의 합이다.

총 가격 $c$ 가 $k \le c \le 2k$ 를 만족하는 직사각형 필지가 존재하는지 판정하여라.

입력

첫째 줄에 두 정수 $k$ 와 $n$ 이 주어진다 ( $1 \le k \le 10^9$ , $1 \le n \le 2000$ ).

다음 $n$ 개의 줄에는 각각 $n$ 개의 음이 아닌 정수가 주어진다. $j{+}1$ 번째 줄의 $i$ 번째 수는 열 $i$ , 행 $j$ 에 위치한 단위 정사각형의 가격이다. 모든 가격은 $2 \cdot 10^9$ 이하이다.

출력

총 가격 $c$ 가 $k \le c \le 2k$ 를 만족하는 직사각형 필지가 존재하면 YES를, 그렇지 않으면 NO를 출력한다.

예제3

예제 1

입력

예상 출력

YES

예제 2
입력
```
5 1
5
```
예상 출력
```
YES
```
예제 3
입력
```
10 2
3 4
5 6
```
예상 출력
```
YES
```