Weekend Trip Plan

Youngseon wants to visit exactly one travel destination and one lodging over the weekend.

The region has $n$ key locations connected by bidirectional roads, each with a travel distance. Every location is reachable from every other location by road. Each destination and each lodging sits at one location, and no destination shares a location with a lodging.

Let $w_a$ be the expectation value of destination $a$, $w_b$ the expectation value of lodging $b$, and $dist(a, b)$ the shortest road distance between them. The score of a plan is

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

Choose the pair with the largest score and compute that maximum. The route between the two locations may pass through other destinations or lodgings.

The first line contains the number of locations $n$ ($2 \le n \le 1000$).

The next $n$ lines give an adjacency matrix. The $j$-th number on the $i$-th line, $d_{ij}$, is the road distance between location $i$ and location $j$. A value of $0$ means there is no direct road ($0 \le d_{ij} \le 5000$, $d_{ij} = d_{ji}$, $d_{ii} = 0$).

The next line contains the number of destinations $p$ and the number of lodgings $q$ ($1 \le p, q \le n$, $2 \le p + q \le n$).

The next $p$ lines each give a destination location number and its expectation value. The following $q$ lines each give a lodging location number and its expectation value. Location numbers are between $1$ and $n$ inclusive, and every expectation value is between $1$ and $5000$ inclusive.

Print the maximum value of $w_a + w_b - dist(a, b)$ over all destination and lodging pairs. If every pair scores a negative value, print the largest (closest to zero) of them.