P2570 [ZJOI2010] The Gluttonous Mice

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.

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 $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}$.

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