$$$\qquad$$$Cosmo Go is Chief Coordinator Beeblebrox's favorite game, and, by the way, he does not like to lose. According to Cosmo Go rules, the game field is a rectangular goban, separated by vertical and horizontal lines. Standard cosmic goban consists of $$$N$$$ x $$$N$$$ cells in the Cartesian coordinate system $$$(x, y)$$$, where $$$(1 \leq x, y \leq N)$$$.

$$$\qquad$$$Each cell can contain one of three following objects: locked cells, empty cells, or Go-isi. They're painted in red, green, and white colors appropriately. For each $$$i$$$, $$$(1 \leq i \leq N)$$$, in the $$$i$$$-th column, cells from the bottommost row to the $$$A_i$$$-th row from the bottom — are red cells showing locked cells.

$$$\qquad$$$$$$M$$$ white cells are showing Go-isi. Each Go-isi has its own positive integer deleting cost. $$$j$$$-th white cell $$$(1 \leq j \leq M)$$$ is the cell $$$(X_j, Y_j)$$$. All the other cells are green, showing empty cells.

The rectangular region is fortified if it satisfies the following conditions:

$$$\qquad$$$1. There are no red cells inside the region.

$$$\qquad$$$2. There are two or more white pixels inside the region.

$$$\qquad$$$To win, Beeblebrox has to delete all fortified regions (each deletion is considered a turn). Beeblebrox always wants to set records. To achieve the best results, he has to reach the minimum cost of all turns. Beeblebrox has trouble figuring out protected areas, And he asked you to write a program that will help him identify and destroy protected areas.

$$$\qquad$$$You enthusiastically volunteered to help Beeblebrox solve such an interesting problem.