[ZJOI2010] 贪吃的老鼠
题目描述
奶酪店里最近出现了 $m$ 只老鼠!它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产 $n$ 块奶酪,其中第 $i$ 块的大小为 $p_i$,会在第 $r_i$ 秒被生产出来,并且必须在第 $d_i$ 秒之前将它吃掉。第 $j$ 只老鼠吃奶酪的速度为 $s_j$,因此如果它单独吃完第 $i$ 块奶酪所需的时间为 $p_i/s_j$。老鼠们吃奶酪的习惯很独特,具体来说:
1. 在任一时刻,一只老鼠最多可以吃一块奶酪;
2. 在任一时刻,一块奶酪最多被一只老鼠吃。
由于奶酪的保质期常常很短,为了将它们全部吃掉,老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长 $T$ 秒是指所有的奶酪的 $d_i$ 变成 $d_i+T$。同时,使用魔法的代价很高,因此老鼠们希望找到最小的 $T$ 使得可以吃掉所有的奶酪。
输入输出格式
输入格式
输入文件的第一行包含一个整数 $K$,表示输入文件中数据的组数。
每组数据的第一行包含两个整数 $n$ 和 $m$,分别表示奶酪和老鼠的数量。接下来的 $n$ 行每行包含三个整数 $p_i,r_i,d_i$。最后 $m$ 行每行包含一个整数,表示 $s_j$。$p_i,r_i,d_i,s_j$ 的含义如上文所述。
输出格式
包含 $K$ 行,每行包含一个实数,表示你找到的最小的 $T$。你的答案和标准答案的绝对误差不应超过 $10^{-4}$。
输入输出样例
输入样例 #1
2
2 2
13 0 4
10 1 3
4
2
1 1
1 0 2
1
输出样例 #1
0.5
0
说明
### 样例说明
第一组数据中:
第 $0$ 到第 $1$ 秒:
第一只老鼠吃第一块奶酪;
第 $1$ 到第 $3.5$ 秒:
- 第一只老鼠吃第二块奶酪;
- 第二只老鼠吃第一块奶酪;
第 $3.5$ 到第 $4.5$ 秒:第一只老鼠吃第一块奶酪。
### 数据规模
$30\%$ 的数据中,$1 \le n,m \le 5$;
$100\%$ 的数据中,$1 \le K \le 5$,$1 \le n,m \le 30$,$1 \le p_i \le 10^5$,$0 \le r_i<d_i \le 10^7$,$1 \le s_j \le 10^5$。