There are $m$ mice in a cheese shop! Their goal is to eat all the cheese produced. The shop produces $n$ pieces of cheese in a day. The $i$-th piece has size $p_i$, is produced at time $r_i$, and must be eaten before time $d_i$. The $j$-th mouse eats cheese at a speed of $s_j$, so the time it takes for this mouse to eat the $i$-th piece of cheese alone is $p_i/s_j$. The mice have unique eating habits:

(1) At any given time, a mouse can eat at most one piece of cheese; (2) At any given time, a piece of cheese can be eaten by at most one mouse.

Since the shelf life of the cheese is often very short, the mice need to use a magical spell to extend the shelf life of the cheese to ensure they can eat it all. Extending the shelf life by $T$ seconds means that for all cheese, $d_i$ becomes $d_i + T$. Since using magic is very costly, the mice want to find the minimum $T$ such that all the cheese can be eaten.

Input

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

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

Output

The output file contains $K$ lines, each containing a real number representing the minimum $T$ found. Your answer and the standard answer should not have an absolute error exceeding $10^{-4}$.

Examples

Input 1

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

Output 1

0.5
0

Note

In the first test case: From time 0 to 1: The first mouse eats the first piece of cheese; From time 1 to 3.5: The first mouse eats the second piece of cheese; The second mouse eats the first piece of cheese; * From time 3.5 to 4.5: The first mouse eats the first piece of cheese.

Constraints

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