Lefkaritika

"Lefkaritika" are traditional handmade lace designs and the characteristic embroidery art of Cyprus. Lace making in the village of Lefkara goes back to the fourteenth century. Local craft, the embroidery of the Venetian courtiers who ruled the island in 1489, and ancient Greek and Byzantine geometric patterns all shaped it, and every design is made by hand from four basic elements: the hemstitch, cut work, satin stitch fillings and needlepoint edgings.

The craft is still the main occupation of the women in the village. They make tablecloths, napkins and show pieces while sitting together and talking in the narrow streets or on covered patios. A young girl picks it up over years of informal exposure, then learns from her mother or grandmother how to apply cotton thread to linen. Once a lace maker knows the art thoroughly, she designs work that carries both the tradition and her own personality. Lace making is at the center of daily life for the women of Lefkara and a proud symbol of their identity.

"Lefkaritika" were inscribed on the Representative List of the Intangible Cultural Heritage of Humanity in 2009. They are recorded in the Heritage Archives of the Municipality of Lefkara, in the Archives of Oral Tradition of the Scientific Research Centre of Cyprus, and in the National Heritage Index.

Pantelis owns a small souvenir shop in Lefkara. He inherited a large collection of square "Lefkaritika" from his grandmother and wants to store them in the shop's storeroom. The storeroom is not large enough, so he will have to place some items on top of others. He wants to know how many items he can put down at once.

The floor of the storeroom is a grid of $W \times L$ points with integer coordinates. Write $(x, y)$ for the point in column $x$ and row $y$, where $1 \le x \le W$ and $1 \le y \le L$. A light bulb hangs directly above some of these points.

The rules for placing items are:

• Items are square and their sides are parallel to the axes. Every integer side length is available, with no limit on the number of pieces. The smallest item has side 1.
• An item of side $k$ is placed with its top left corner on a point $(x, y)$, and it then covers every point $(a, b)$ with $x \le a \le x + k$ and $y \le b \le y + k$.
• An item must fit completely inside the storeroom, so $x + k \le W$ and $y + k \le L$. The largest item can cover the whole room when the bulbs allow it.
• No item may cover a point that has a light bulb above it, including a point on its border. Otherwise the lace is damaged.
• Larger items are placed first. Items may overlap, and a smaller item may lie on top of a larger one and cover it completely.
• No item may completely cover another item of exactly the same size, so two items of the same side length cannot be placed at the same point.

The picture below is a storeroom with $W = 4$ and $L = 3$, drawn as a grid of points. A point with a bulb above it is drawn as O and a free point as a dot. The bulbs are at $(2, 2)$ and $(3, 3)$.

Only one item fits here, the item of side 1 whose top left corner is $(3, 1)$. Every other placement covers a point that lies under a bulb.

• The first line has two integers $W$ and $L$, the width and the length of the storeroom floor counted in grid points ($1 \le W, L \le 2000$).
• The second line has one integer $B$, the number of light bulbs ($0 \le B \le W \times L$).
• Each of the next $B$ lines has two integers $x_i$ and $y_i$, the coordinates of the $i$th light bulb ($1 \le x_i \le W$, $1 \le y_i \le L$). No two bulbs hang above the same point.

Print one line with the largest number of items that can be placed in the storeroom at once. The answer can be larger than a 32-bit integer holds.

In the first example the storeroom has $W = 4$ and $L = 5$, and the bulbs are at $(1, 4)$, $(1, 5)$ and $(4, 1)$. Three items of side 2 fit, as in image 3. An item of side 1 may lie on an item of side 2 but not on another item of side 1, so nine more items fit as in image 4. That is twelve items in total.