주말 여행 계획

영선이는 주말을 이용해 여행지 한 곳과 숙소 한 곳을 방문하려고 한다.

지역에는 주요 지점 $n$개가 있고, 지점 사이에는 양방향 도로가 있다. 각 도로에는 이동 거리가 표시되어 있다. 모든 지점은 도로를 통해서 서로 오갈 수 있다. 여행지와 숙소는 각각 어느 한 지점에 있으며, 여행지가 있는 지점과 숙소가 있는 지점은 서로 다르다.

여행지 $a$의 기대치를 $w_a$, 숙소 $b$의 기대치를 $w_b$, 두 지점 사이의 최단 도로 거리를 $dist(a, b)$라고 하자. 여행 계획의 점수는 다음과 같다.

$score(a, b) = w_a + w_b - dist(a, b)$

점수가 가장 큰 여행지와 숙소의 쌍을 골라 그 점수를 구하라. 두 지점을 오가는 경로가 다른 여행지나 숙소를 지나도 된다.

첫째 줄에 지점의 개수 $n$이 주어진다 ($2 \le n \le 1000$).

이어지는 $n$줄에는 인접 행렬이 주어진다. $i$번째 줄의 $j$번째 수 $d_{ij}$는 $i$번 지점과 $j$번 지점 사이의 도로 거리이다. $d_{ij}$가 $0$이면 그 사이를 직접 연결하는 도로는 없다 ($0 \le d_{ij} \le 5000$, $d_{ij} = d_{ji}$, $d_{ii} = 0$).

다음 줄에는 여행지의 개수 $p$와 숙소의 개수 $q$가 주어진다 ($1 \le p, q \le n$, $2 \le p + q \le n$).

이어지는 $p$줄에는 여행지가 있는 지점 번호와 기대치가 주어진다. 이어지는 $q$줄에는 숙소가 있는 지점 번호와 기대치가 주어진다. 지점 번호는 $1$ 이상 $n$ 이하이고, 기대치는 $1$ 이상 $5000$ 이하이다.

여행지 하나와 숙소 하나를 골랐을 때의 $w_a + w_b - dist(a, b)$ 값 중 가장 큰 값을 출력한다. 모든 쌍의 값이 음수이면 그중 가장 큰 음수 값을 출력한다.