Processor

A processor supports dynamic speed scaling: it can run at any positive integer speed, but a higher speed draws more power. To run a set of programs energy-efficiently, we want a schedule that minimizes the maximum speed the processor ever uses.

The processor must run $n$ programs. Each program $P_i$ has a release time $r_i$, a deadline $d_i$, and an amount of work $w_i$. All of the work $w_i$ must be performed inside the interval $[r_i, d_i]$. The processor is preemptive: it may pause the running program and later resume it from the exact point where it stopped, so a program need not run over one contiguous interval. If $P_i$ runs at a constant speed $s$, it finishes in $w_i / s$ time. The processor runs at most one program at any instant and may change speed over time, but only at positive integer speeds. Speed is unbounded, so every program can always be completed.

Find a schedule that completes all programs and minimizes the maximum speed at which the processor runs.

For example, take five programs with intervals $[r_i, d_i]$ and work $w_i$: $[1, 4]$ with $w_1 = 2$, $[3, 6]$ with $w_2 = 3$, $[4, 5]$ with $w_3 = 2$, $[4, 7]$ with $w_4 = 2$, and $[5, 8]$ with $w_5 = 1$. The figure below shows a schedule whose maximum speed is $2$, which is optimal for this instance.

Figure 1

The first line contains the number of test cases $T$ ($1 \le T \le 20$).

Each test case starts with a line containing an integer $n$ ($1 \le n \le 10000$), the number of programs. Each of the next $n$ lines contains three integers $r_i$, $d_i$, and $w_i$: the release time, the deadline, and the work of program $P_i$, where $1 \le r_i < d_i \le 20000$ and $1 \le w_i \le 1000$.

For each test case, print exactly one line: the minimum possible value of the maximum speed, taken over all schedules that complete every program on time.