도로

네덜란드의 그린 하트 지역은 마을이 작고 길이 좁다. 어떤 길은 폭이 차 한 대뿐이어서 마주 오는 두 차가 만나면 오도 가도 못한다. 길 양옆으로 운하가 흘러 어느 쪽도 길 밖으로 비켜 줄 수 없다. 그래서 길 곳곳을 조금씩 넓혀 두었고, 이렇게 넓힌 자리를 대피소라고 하자. 대피소에서는 차 한 대가 옆으로 비켜서고 반대편에서 오는 차가 한 대 이상 지나간다. 통행량이 적을 때는 이것으로 충분하다. 짧은 시간에 양쪽에서 차가 몰리면 길이 막힌다.

이런 길에서 가장 좋은 통행 계획을 찾는 일은 꽤 어렵다. 그래서 이 문제는 더 쉬운 것을 묻는다. 길은 동서로 뻗어 있다. 동쪽으로 가는 차는 서쪽 끝에서 들어와 동쪽 끝으로 나가고, 서쪽으로 가는 차는 그 반대다. 대피소의 위치, 동쪽으로 가는 차의 수 $e$, 서쪽으로 가는 차의 수 $w$, 그리고 통행표가 주어진다. 통행표는 동쪽으로 가는 차와 서쪽으로 가는 차의 모든 쌍에 대해 두 차가 서로 지나치는 지점을 알려 준다.

지점 $z$에서 지나치는 두 차는 그 순간 둘 다 $z$에 있다. 즉 상대가 $z$에 도착하기 전에는 어느 쪽도 $z$를 지나 더 나아가지 못한다.

모든 차는 처음부터 들어갈 준비를 마쳤고, 운전자는 되도록 빨리 길을 빠져나가려 한다. 차는 멈춰 서 있거나 시속 45km로 달리며, 출발과 정지에는 시간이 걸리지 않는다. 같은 방향으로 가는 차끼리는 항상 25m 이상 거리를 두고 서로 앞지르지 않으며, 기다리는 동안 길 위에 줄지어 서 있어도 된다. 서로 다른 두 대피소 사이의 거리는 30m 이상이다. 차의 길이는 무시한다.

첫 번째 차가 길에 들어선 순간부터 마지막 차가 길을 빠져나가는 순간까지의 시간을 재고, 그 간격을 가장 짧게 만들려고 한다.

첫 줄에 테스트 케이스의 수 $n$이 주어진다. 각 테스트 케이스는 다음과 같이 이루어진다.

• 길의 길이 $l$ ($0 < l \le 30000$, 단위는 미터)과 대피소의 수 $p$ ($0 < p$)가 한 줄에 주어진다.
• 각 대피소가 길의 서쪽 끝에서 떨어진 거리를 미터 단위 양의 정수 $p$개로, 증가하는 순서로 한 줄에 준다.
• 동쪽으로 가는 차의 수 $e$와 서쪽으로 가는 차의 수 $w$ ($0 < e, w \le 1000$)가 한 줄에 주어진다.
• 수 $w$개가 적힌 줄이 $e$개 이어진다. $y$번째 줄 ($1 \le y \le e$)의 $x$번째 수 $z$ ($1 \le x \le w$, $0 \le z \le p + 1$)는 동쪽으로 가는 $y$번 차와 서쪽으로 가는 $x$번 차가 지점 $z$에서 서로 지나친다는 뜻이다. 지점 $i$ ($1 \le i \le p$)는 둘째 줄에 주어진 $i$번째 대피소이고, 지점 $0$은 서쪽 끝, 지점 $p + 1$은 동쪽 끝이다. $z = 0$은 $x$번 차가 길을 빠져나간 뒤에 $y$번 차가 길에 들어선다는 뜻이고, $z = p + 1$은 $y$번 차가 길을 빠져나간 뒤에 $x$번 차가 들어선다는 뜻이다.

서쪽으로 가는 $x$번 차는 $x + 1$번 차보다 먼저 길에 들어서고, 동쪽으로 가는 $y$번 차는 $y + 1$번 차보다 먼저 들어선다. 한 줄에 있는 수는 하나 이상의 공백으로 구분한다.

각 테스트 케이스마다 한 줄에 수 하나를 출력한다. 주어진 통행표를 지키는 가장 빠른 통행에서, 첫 번째 차가 길에 들어선 순간부터 마지막 차가 빠져나가는 순간까지 걸린 시간을 초 단위로 재어 가장 가까운 정수로 반올림한 값이다. 모든 거리가 정수 미터이고 시속 45km는 초속 12.5m이므로, 정확한 시간은 언제나 0.08초의 배수이고 두 정수의 한가운데에 놓이는 일은 없다.