프로세서

프로세서는 동적 속도 조절을 지원한다. 임의의 양의 정수 속도로 동작할 수 있지만, 속도가 높을수록 전력 소모가 커진다. 여러 프로그램을 전력 효율적으로 실행하려면, 프로세서가 사용하는 최대 속도를 최소로 만드는 스케줄이 필요하다.

프로세서는 $n$개의 프로그램을 실행해야 한다. 각 프로그램 $P_i$에는 시작 시각 $r_i$, 마감 시각 $d_i$, 작업량 $w_i$가 주어진다. 작업량 $w_i$ 전체는 반드시 구간 $[r_i, d_i]$ 안에서 처리되어야 한다. 프로세서는 선점형이다. 즉, 실행 중인 프로그램을 잠시 멈췄다가 나중에 멈춘 지점부터 이어서 실행할 수 있으므로, 한 프로그램을 반드시 연속된 한 구간에서 실행할 필요는 없다. 프로그램 $P_i$를 일정한 속도 $s$로 실행하면 $w_i / s$의 시간이 걸린다. 프로세서는 어느 순간에도 최대 한 개의 프로그램만 실행하며, 시간에 따라 속도를 바꿀 수 있지만 속도는 항상 양의 정수여야 한다. 속도에는 상한이 없으므로 모든 프로그램은 언제나 완료할 수 있다.

모든 프로그램을 완료하면서 프로세서가 사용하는 최대 속도를 최소로 만드는 스케줄을 구하라.

예를 들어, 구간 $[r_i, d_i]$와 작업량 $w_i$가 다음과 같은 다섯 개의 프로그램을 생각하자. $[1, 4]$에 $w_1 = 2$, $[3, 6]$에 $w_2 = 3$, $[4, 5]$에 $w_3 = 2$, $[4, 7]$에 $w_4 = 2$, $[5, 8]$에 $w_5 = 1$. 아래 그림은 최대 속도가 $2$인 스케줄을 보여 주며, 이 예시에서는 이 값이 최적이다.

그림 1

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 20$).

각 테스트 케이스의 첫째 줄에는 프로그램의 수를 나타내는 정수 $n$이 주어진다 ($1 \le n \le 10000$). 이어지는 $n$개의 줄 중 $i$번째 줄에는 세 정수 $r_i$, $d_i$, $w_i$가 주어지며, 각각 프로그램 $P_i$의 시작 시각, 마감 시각, 작업량을 뜻한다. 이때 $1 \le r_i < d_i \le 20000$이고 $1 \le w_i \le 1000$이다.

각 테스트 케이스마다 한 줄에, 모든 프로그램을 제때 완료하는 스케줄들 중에서 최대 속도가 될 수 있는 최솟값을 출력한다.