부지 구매

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를 출력한다.