이것은 전쟁이다

군대가 전쟁에 나가려 한다. 지휘관은 군인들을 여러 그룹으로 나누어 전체 전투력의 합이 최대가 되게 하려 한다. $N$명의 군인을 x축 위의 점으로 본다. 모든 군인은 서로 다른 위치에 서 있고, $i$번째 군인은 $x_i$에 서 있다. 군인은 1번부터 $N$번까지 번호가 붙어 있으며, x 값 순서대로 왼쪽에서 오른쪽으로 정렬되어 주어진다.

군인들을 하나 이상의 그룹으로 나눈다. 각 군인은 정확히 한 그룹에 속하며, 모든 그룹은 연속된 구간이어야 한다. $a \le b$인 구간 $[a, b]$가 하나의 그룹이면, 이 그룹은 $a$번째부터 $b$번째 군인까지(양 끝 포함) 모두 포함하고, 다른 그룹의 군인이 그 사이에 끼지 않는다.

각 군인 $i$에게는 함수 $f_i$가 주어진다. 이 함수는 군인 $i$가 자기 그룹에서 가장 왼쪽에 있을 때만 쓴다. $a$번째부터 $b$번째까지 그룹의 전투력은 $f_a(x_b)$이다. 즉 그룹에서 가장 오른쪽 군인의 x 값을 가장 왼쪽 군인의 함수에 넣은 값이다.

정렬된 서로 다른 $M$개의 값 $z_1, z_2, \dots, z_M$과, 각 함수에 대해 $f_i(z_j)$ 값이 주어진다. 이 $M$개 값이 아닌 $z$에 대해서는 연속한 점 $(z_j, f_i(z_j))$를 직선 선분으로 잇는다. 그러면 각 $f_i$는 $z_1$부터 $z_M$까지 정의된다.

군대의 전투력은 모든 그룹 전투력의 합이다. 이 합이 최대가 되도록 그룹을 나누고 그 값을 구한다.

첫 줄에 테스트 케이스 수 $T$($1 \le T \le 100$)가 주어진다. 각 테스트 케이스는 다음과 같다.

첫 줄에 두 정수 $N$과 $M$($1 \le N \le 10^5$, $2 \le M$, $N \times M \le 10^5$)이 주어진다. 다음 줄에 정렬된 정수 $x_1, x_2, \dots, x_N$($-10^6 \le x_i \le 10^6$)이 주어진다. 다음 줄에 정렬된 정수 $z_1, z_2, \dots, z_M$($-10^6 \le z_j \le 10^6$)이 주어진다. 다음 $N$개 줄에는 각각 $M$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $f_i(z_j)$이다($-10^6 \le f_i(z_j) \le 10^6$).

$z_1 \le x_1$이고 $x_N \le z_M$이 보장된다.

각 테스트 케이스마다 군대의 최대 전투력을 한 줄에 출력한다. 값은 소수점 아래 정확히 6자리로 반올림한다.

다음 그림은 첫 번째 테스트 케이스를 나타낸다.

x축 위의 채워진 원 3개는 3명의 군인 위치이다. 위에서 설명한 방식으로 그린 함수 $f_1$, $f_2$, $f_3$가 군인마다 하나씩 있다. 최선의 방법은 처음 두 군인을 한 그룹으로 묶고, 마지막 군인은 혼자 두는 것이다. 첫 그룹의 전투력은 $f_1(x_2)$이며, $f_1(2) = 4$이다. 마지막 군인 그룹의 전투력은 $f_3(x_3) = f_3(3) = 2.666667$이다. 따라서 전체 전투력은 6.666667이다(소수점 여섯째 자리까지 반올림한 값).