시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 62 18 16 36.364%

문제

정수로 이루어진 N×M(1≤N, M≤500) 크기의 2차원 배열이 있다. 이러한 2차원 배열이 정돈되어 있다는 말은, 1≤i<k≤m, 1≤j<l≤n를 만족하는 모든 i, j, k, l 에 대해서 A[i][j]+A[k][l]≤A[i][l]+A[k][j]가 성립하는 경우를 말한다.

2차원 배열이 주어졌을 때, 이러한 배열이 정돈된 배열인지 확인하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 개수 T(1≤T≤10)가 주어진다. 다음 줄에는 배열에 대한 입력이 T개 주어진다. 각 배열에서 첫째 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열의 각 원소가 주어진다. 입력은 A[1][1], A[1][2], …, A[1][M], A[2][1], A[2][2], …, A[2][M], …, A[N][M] 순서대로 주어진다.

출력

T개의 줄에, 주어진 순서대로 답을 출력한다. 정돈된 배열인 경우에는 YES를 출력하고, 아닌 경우에는 NO를 출력한다. 반드시 대소문자에 주의하도록 한다.

예제 입력

2
2 3
1 1 1
1 1 1
3 2
1 1
1 2
1 1

예제 출력

YES
NO

힌트