2142번 - 정돈된 배열

문제

정수로 이루어진 N×M 크기의 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가 주어진다. 다음 줄에는 배열에 대한 입력이 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를 출력한다. 반드시 대소문자에 주의하도록 한다.

제한

• 1 ≤ T ≤ 10
• 1 ≤ N, M ≤ 500
• -1,000,000 ≤ A[i][j] ≤ 1,000,000

힌트