Tourist in Sevastopol
Legendary Sevastopol,
Impregnable to enemies.
Sevastopol, Sevastopol –
Pride of our 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 task. 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×M, where each cell contains a certain number of landmarks. Our tourist aims to view as many landmarks as possible, starting from any cell in the Northern row and finishing in any cell in the Southern 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 hadn't already identified the most interesting places in Sevastopol online. Naturally, he now wants to visit all of them. Your task is to assist him: given a map with landmarks and a list of specific places the tourist wants to see, determine the maximum number of landmarks he can visit. If it is impossible to visit all the desired places while moving only in the specified directions, output -1. The tourist must remain within the city limits.
Input
The first line contains two numbers N, M (1 ≤ N, M ≤ 1000) – the dimensions of the city grid. This is followed by N rows, each containing M numbers, representing the number of landmarks in each section (let's be honest, there are no more than 10^5 landmarks in each section, but no fewer than one, as the natural beauty here is remarkable). Next, a number K (0 ≤ K ≤ N·M) is given, indicating the number of sections the tourist wishes to visit. The following K lines each contain two numbers, representing the coordinates of the i-th section. It is guaranteed that sections do not repeat in his list.
Output
Output a single line with the answer to the problem, or "-1" if it is impossible to tour Sevastopol while visiting all the desired places.