시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 193 25 21 16.031%

문제

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

각각의 스포츠 경기 Ei(1 ≤ i ≤ n)의 시작 시간은 si, 경기 시간은 di, 경기장은 gi이다. gi에서 gj로 가는 이동 시간은 ti,j(1 ≤ i,j ≤ n)이며, ti,j = tj,i와 ti,j ≤ ti,k + tk,j (1 ≤ i,j,k ≤ n)을 만족한다.

리포터는 경기가 열리는 동안 그 경기장에서 계속 취재를 해야 한다. 즉, 한 리포터가 두 경기 Ei와 Ej를 취재하려면, si + di + ti,j ≤ sj 나 sj + dj + tj,i ≤ si를 만족해야 한다.

경기 정보가 모두 주어졌을 때, 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 경기의 수 n (1 ≤ n ≤ 1,000)이 주어진다. 둘째 줄에는 각 경기의 시작 시간 si, 셋째 줄에는 경기 시간 di가 주어진다. (1 ≤ si, di ≤ 1,000,000) 넷째 줄부터 총 n개 줄 중 i번째 줄에는 n-i+1개의 정수가 주어지며, ti,i, ti,i+1, ..., ti,n을 나타낸다. (0 ≤ ti,j ≤ 1,000,000) ti,i는 항상 0이다.

출력

각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄은 한 리포터가 동시에 취재할 수 없는 가장 큰 경기의 부분집합의 크기 k이고, 둘째 줄에는 집합에 포함된 경기의 번호를 출력한다. (Ei에서 i) 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

예제 입력

2
3
7 8 9
1 1 1
0 2 2
0 1
0
2
7 12
3 2
0 2
0

예제 출력

3
2 3 1
1
2

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2012 K번