贪吃的老鼠

题目描述:

奶酪店里最近出现了m只老鼠！它们的目标就是把生产出来的所有奶酪都吃掉。奶酪店中一天会生产n块奶酪，其中第i块的大小为p_i，会在第r_i秒被生产出来，并且必须在第d_i秒之前将它吃掉。第j只老鼠吃奶酪的速度为s_j，因此如果它单独吃完第i快奶酪所需的时间为p_i/s_j。老鼠们吃奶酪的习惯很独特，具体来说：

• 在任一时刻，一只老鼠最多可以吃一块奶酪；
• 在任一时刻，一块奶酪最多被一只老鼠吃。

         由于奶酪的保质期常常很短，为了将它们全部吃掉，老鼠们需要使用一种神奇的魔法来延长奶酪的保质期。将奶酪的保质期延长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。

样例输入:

2
2 2
13 0 4
10 1 3
4
2
1 1
1 0 2
1

样例输出:

0.5
0

提示:

样例说明

         第一组数据中：

• 第0到第1秒：第一只老鼠吃第一块奶酪；
• 第1到第5秒：
• 第一只老鼠吃第二块奶酪；
• 第二只老鼠吃第一块奶酪；
• 第5到第4.5秒：第一只老鼠吃第一块奶酪。

 

数据规模

         30%的数据中，1<=n，m<=5；

         100%的数据中，1<=k<=5, 1<=n,m<=30, 1<=p_i<=10⁵,1<=r_i<d_i<=10⁷, 1<=s_j<=10⁵。

时间限制: 10000ms
空间限制: 256MB

---

来源: 浙江省选2010day2t3