题目描述

奶酪店里最近出现了 $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}$。

2
2 2
13 0 4
10 1 3
4
2
1 1
1 0 2
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$。