설치 작업

어느 통신 회사의 서비스 기사는 아침마다 그날 처리할 작업 목록을 받는다. 전화, 인터넷, IPTV를 설치하거나 이미 설치된 설비의 고장을 수리하는 일이다. 각 작업에는 고객이 원하는 완료 기한이 있지만, 작업량이 많아 모든 기한을 지키지는 못할 수 있다.

기사는 한 번에 하나의 작업만 처리한다. 각 작업 $J_i$ 에는 처리 시간 $s_i$ 와 기한 $d_i$ 가 주어진다. 시각 $0$ 에서 시작해 작업들을 어떤 순서로 하나씩 이어서 처리하며, 한 번 시작한 작업은 끝까지 처리한다. 작업 $J_i$ 가 시각 $C_i$ 에 끝나면 그 벌점은 $\max(0, C_i - d_i)$, 즉 기한을 얼마나 넘겼는지로 정의된다. 모든 값은 $0 < s_i \le d_i$ 를 만족하는 양의 정수이다.

벌점이 가장 큰 두 작업의 벌점 합이 최소가 되도록 작업 순서를 정하라.

예를 들어 $i = 1, \dots, 6$ 에 대해 $(s_i, d_i)$ 가 각각 $(1, 7), (4, 7), (2, 4), (2, 15), (3, 5), (3, 8)$ 인 여섯 개의 작업을 생각하자. 그림 1은 가장 큰 두 벌점의 합을 최소로 만드는 한 스케줄을 보여 준다. 여기서 가장 큰 두 벌점은 $J_2$ 와 $J_6$ 의 것으로 각각 $6$ 과 $1$ 이며, 그 합은 $7$ 이다.

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

각 테스트 케이스의 첫째 줄에는 작업의 수 $n$ ($1 \le n \le 500$) 이 주어진다. 이어지는 $n$ 개의 줄 중 $i$ 번째 줄에는 작업 $J_i$ 의 처리 시간 $s_i$ 와 기한 $d_i$ ($1 \le s_i \le d_i \le 10000$) 가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 최적 스케줄에서 가장 큰 두 벌점의 합을 한 줄에 출력한다.