Tourist in Sevastopol#4547
Legendary Sevastopol,
Impregnable to enemies.
Sevastopol, Sevastopol –
Pride of sailors ...
Sevastopol (historically known as Chersonesus in ancient Greek) is a city of national importance in Ukraine, recognized as a hero city. It is situated in the southwestern part of the Crimean Peninsula, along the coast of the Black Sea, with its historical center located on the southern side of Sevastopol Bay.
Sevastopol is rich in notable landmarks: the ancient city of Chersonesus, the Monument to the Sunken Ships, Malakhov Kurgan, the Monument to Sailor Koshka, and many more. Visitors often remark that at every turn, there is something new, intriguing, and unique to discover. And they are mostly right.
Now, let's proceed to the problem. This will be particularly useful for tourists who have limited time and can only take a quick look at some landmarks. We will represent the city as a rectangular grid of size N \times M, where each cell contains a certain number of landmarks. Our tourist aims to visit as many landmarks as possible, starting from any cell in the northernmost row and finishing in any cell in the southernmost row. The tourist can move in only three directions: south, southwest, and southeast. Remember, north is at the top of the map, and south is at the bottom.
This task would be straightforward if the tourist had not already found the most interesting places in Sevastopol online. Naturally, the tourist now wants to visit all of them. Your task is to assist: given a map showing the number of landmarks in each section and a list of specific places that the tourist wants to see, determine the maximum number of landmarks they can visit while visiting all the desired places. If it is impossible to visit all specified places while moving only in the allowed directions, output . The tourist cannot leave the city limits.
The first line contains two integers , (1 \leq N, M \leq 1000) – the dimensions of the city grid. The next lines each contain integers, where each integer represents the number of landmarks in a section. (In each section, there are at most 10^5 landmarks, and at least one landmark.)
The next line contains an integer (0 \leq K \leq N \cdot M) – the number of sections the tourist wishes to visit. The following lines each contain two integers, the coordinates of a desired section (rows are numbered from 1 to , columns from 1 to ). It is guaranteed that sections do not repeat in this list.
Print a single integer: the maximum number of landmarks the tourist can visit while visiting all the desired places, or if it is impossible.
Example 1