Minimum Security Cost for Peace Roads

On the distant planet of Alienfent, there exists a thriving civilization that marks every location using latitude and longitude. The planet is divided into \(n\) latitudinal bands (from north to south) and \(m\) longitudinal segments (from west to east). At each intersection of a latitude and a longitude, there is a country, denoted by \((i,j)\) with \(1\leq i\leq n\) and \(1\leq j\leq m\) (a total of \(n\times m\) countries).

Every pair of countries that are adjacent in longitude or latitude is connected by a bidirectional road. In detail:

• Longitude-adjacent roads: For every country \((i,j)\), there is a road between \((i,j)\) and \((i,j+1)\). Note that when \(j = m\), the road connects \((i,m)\) and \((i,1)\) (i.e. the longitudinal direction is circular).
• Latitude-adjacent roads: For every country \((i,j)\) with \(1\leq i < n\), there is a road connecting \((i,j)\) and \((i+1,j)\). (The polar regions are not adjacent.)

During a series of \(q\) centuries, world wars break out. In the \(i\)th century, every country whose longitude is in the interval \([l_i, r_i]\) is involved in the war and is considered dangerous. A country that is not involved in the war is called peaceful.

A road is considered a peace road if both the countries at its ends are peaceful. For safety, the Alienfent United Government chooses to open only some of the peace roads, such that every pair of peaceful countries is connected (directly or indirectly) via the opened roads. Each road has a distinct security cost, and keeping a road open requires paying its cost. Your task is to help the government choose a subset of peace roads that connects all peaceful countries (if any) and minimizes the sum of their security costs.

Note: After each century, the war is over and the set of countries engaged in war is independent from that of any other century.

The answer for each century is defined as follows:

• If there are zero or one peaceful countries, the required cost is \(0\).
• If it is impossible to connect all peaceful countries using peace roads, output \(-1\).
• Otherwise, output the minimum total security cost required to choose a set of peace roads that connects all peaceful countries.

inputFormat

The first line contains three integers \(n\), \(m\) and \(q\) \((1 \leq n, m \leq 10^3, 1 \leq q \leq 10^4)\) — the number of latitudes, longitudes and the number of centuries (queries).

Then follow \(n\) lines. The \(i\)th of these lines contains \(m\) integers. The \(j\)th integer is the security cost for the road connecting country \((i,j)\) and \((i, j+1)\), where for \(j = m\) the road connects \((i, m)\) and \((i,1)\).

Then follow \(n-1\) lines. The \(i\)th of these lines contains \(m\) integers. The \(j\)th integer is the security cost for the road connecting country \((i,j)\) and \((i+1,j)\).

Finally, each of the next \(q\) lines contains two integers \(l_i\) and \(r_i\) \((1 \leq l_i \leq r_i \leq m)\), describing a query in which every country whose longitude is in the interval \([l_i, r_i]\) is involved in a world war.

outputFormat

For each query, output a single line containing one integer: the minimum total security cost to open a set of peace roads connecting all peaceful countries, or \(-1\) if it is impossible. If there are zero or one peaceful countries, output \(0\).

sample

2 3 2
1 5 3
2 4 6
7 8 9
2 2
1 3

16
0

</p>