Minimum Workload Reassignment for One‐Way Grid to Satisfy Manhattan Requirements

P City in country M features a grid of m horizontal streets and n vertical streets. In this city the streets are one‐way: each horizontal street permits travel only eastward or westward and each vertical street only northward or southward. Initially, every street has a fixed direction and a cost is associated with changing the entire street’s direction; that is, flipping a street from east to west (or vice versa) or north to south (or vice versa) incurs the given workload.

The city mayor has received several complaints from tourists. Each complaint is expressed as a requirement in the following form: For two intersections, the length of the shortest path (measured in number of street segments) must equal the Manhattan distance between them. For any two intersections with coordinates \((x_1,y_1)\) and \((x_2,y_2)\), the Manhattan distance is

\( |x_1-x_2|+|y_1-y_2| \)

The grid intersections are determined as follows: the horizontal streets are numbered from north to south from 1 to \(m\) and the vertical streets are numbered from west to east from 1 to \(n\). An intersection is denoted by \((i,j)\) where \(i\) is the horizontal street number and \(j\) is the vertical street number.

For a requirement from intersection \((a,b)\) to \((c,d)\) (with \(a,b,c,d\) all positive integers), note the following:

• If the movement is purely horizontal or vertical (i.e. \(a=c\) or \(b=d\)), then the corresponding street must be set to the correct direction. Specifically, if \(a=c\) and \(d>b\) then the horizontal street \(a\) must be eastbound, and if \(a=c\) and \(da\) then the vertical street \(b\) must be southbound, and if \(c<a\) it must be northbound.
• If both horizontal and vertical movements are needed (i.e. \(a\neq c\) and \(b\neq d\)), one of these two standard Manhattan paths must be available:
  1. Go first horizontally along row \(a\) (which must have the required direction: east if \(d>b\) or west if \(da\) or northbound if \(c<a\)) to reach \((c,d)\).
  2. Or go first vertically along column \(b\) (which must be southbound if \(c>a\) or northbound if \(cb\) or westbound if \(d<b\)) to reach \((c,d)\).
  In other words, for a requirement with both differences nonzero, at least one of the following must hold:
  (Horizontal street a is set correctly and vertical street d is set correctly) or (vertical street b is set correctly and horizontal street c is set correctly).

Your task is to reassign the street directions (by optionally flipping some streets at the given cost) so that all the requirements are met. Moreover, you need to choose a solution with the minimum total workload. If it is impossible to satisfy all the requirements, output -1.

inputFormat

The input begins with two integers \(m\) and \(n\) representing the number of horizontal and vertical streets respectively.

This is followed by \(m\) lines. Each of these lines contains a character and an integer. The character is either E or W representing the initial direction of the horizontal street (east or west), and the integer is the workload (cost) required to flip that street’s direction.

Then follow \(n\) lines. Each line contains a character and an integer. The character is either N or S representing the initial direction of the vertical street (north or south), and the integer is the cost to flip that street’s direction.

Next is an integer \(q\) indicating the number of requirements.

Finally, there are \(q\) lines, each containing four positive integers: a b c d, representing a requirement from intersection \((a, b)\) to \((c, d)\).

outputFormat

Output a single integer: the minimum total workload required to achieve a reassignment that satisfies all the requirements. If no such assignment exists, output -1.

sample

3 3
E 1
W 2
E 3
N 1
S 2
N 3
2
1 1 1 3
2 1 3 1

1