스포츠 전문 채널 GSK

상근이는 자신의 이름을 딴 스포츠 전문 방송국 GSK를 세웠다. GSK는 곧 열리는 $N$개의 경기를 모두 취재하려고 한다.

각 경기 $E_i$ ($1 \le i \le N$)에는 시작 시간 $s_i$, 진행 시간 $d_i$, 그리고 열리는 경기장 $g_i$가 있다. 따라서 경기 $E_i$는 시각 $s_i$에 시작해 시각 $s_i + d_i$에 끝난다. 경기장 $g_i$에서 $g_j$로 이동하는 데 걸리는 시간은 $t_{i,j}$이며, 모든 $i, j, k$에 대해 $t_{i,j} = t_{j,i}$와 삼각 부등식 $t_{i,j} \le t_{i,k} + t_{k,j}$를 만족한다.

리포터 한 명은 경기가 진행되는 동안 그 경기장에 머물며 계속 취재해야 한다. 따라서 한 리포터가 두 경기 $E_i$와 $E_j$를 모두 취재할 수 있으려면, 한 경기를 끝낸 뒤 다른 경기장으로 이동해 시작 전에 도착할 수 있어야 한다. 즉 $s_i + d_i + t_{i,j} \le s_j$ 또는 $s_j + d_j + t_{j,i} \le s_i$ 가운데 하나가 성립해야 한다. 이 조건을 만족하지 못하는 두 경기는 서로 다른 리포터가 맡아야 한다.

어떤 경기 집합 안의 두 경기를 골라도 한 리포터가 함께 취재할 수 없을 때, 그 집합을 충돌 집합이라고 하자. 경기 정보가 모두 주어졌을 때, 가장 큰 충돌 집합의 크기를 구하는 프로그램을 작성하시오. (딜워스 정리에 의해 이 값은 모든 경기를 취재하는 데 필요한 리포터의 최소 인원과 같다.)

첫째 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 경기의 수 $N$ ($1 \le N \le 1{,}000$)이 주어진다. 둘째 줄에는 각 경기의 시작 시간 $s_1, s_2, \dots, s_N$이, 셋째 줄에는 각 경기의 진행 시간 $d_1, d_2, \dots, d_N$이 공백으로 구분되어 주어진다. ($1 \le s_i, d_i \le 1{,}000{,}000$)

이어서 $N$개의 줄이 이동 시간 행렬을 위쪽 삼각 형태로 나타낸다. 그중 $i$번째 줄에는 $N - i + 1$개의 정수 $t_{i,i}, t_{i,i+1}, \dots, t_{i,N}$이 주어진다. ($0 \le t_{i,j} \le 1{,}000{,}000$, 항상 $t_{i,i} = 0$) 행렬은 대칭이므로 $j < i$인 값은 $t_{i,j} = t_{j,i}$로 얻는다.

각 테스트 케이스마다 가장 큰 충돌 집합의 크기 $k$를 한 줄에 출력한다. 즉 어떤 두 경기도 한 리포터가 함께 취재할 수 없는 경기들의 최대 개수를 출력하면 된다.

(원문제는 그러한 집합에 속한 경기 번호까지 출력하도록 했지만, 그 집합은 여러 가지가 될 수 있어 유일하지 않다. 크기 $k$는 항상 유일하게 정해지므로 이 값만 출력한다.)