Description

Recently, $m$ mice have appeared in the cheese shop. Their goal is to eat all the cheese produced. The shop produces $n$ pieces of cheese per day. The $i$-th piece has size $p_i$, is produced at second $r_i$, and must be eaten before second $d_i$. Mouse $j$ eats at speed $s_j$, so if it eats the $i$-th piece alone, it takes time $p_i / s_j$. The mice have special eating rules:

1. At any moment, a mouse can eat at most one piece of cheese.
2. At any moment, a piece of cheese can be eaten by at most one mouse.

Because the shelf life of cheese is often short, to eat all pieces, the mice can use a magical spell to extend the shelf life. Extending the shelf life by $T$ seconds means every $d_i$ becomes $d_i + T$. Since the spell is costly, the mice want the minimum $T$ such that all cheese can be eaten.

Input Format

The first line contains an integer $K$, the number of test cases.

For each test case, the first line contains two integers $n$ and $m$, the numbers of cheese pieces and mice, respectively. The next $n$ lines each contain three integers $p_i, r_i, d_i$. The final $m$ lines each contain one integer $s_j$. The meanings of $p_i, r_i, d_i, s_j$ are as described above.

Output Format

Output $K$ lines. Each line contains a real number, the minimum $T$ you found. The absolute error between your answer and the standard answer must not exceed $10^{-4}$.

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

0.5
0

Hint

Sample Explanation:

For the first test case:

From second $0$ to second $1$: The first mouse eats the first piece of cheese.

From second $1$ to second $3.5$:

• The first mouse eats the second piece of cheese.
• The second mouse eats the first piece of cheese.

From second $3.5$ to second $4.5$: the first mouse eats the first piece of cheese.

Constraints:

• For $30\%$ of the testdata, $1 \le n, m \le 5$.
• For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5