레프카리티카

"레프카리티카"는 키프로스의 전통 수공예 레이스 도안이고, 이 섬을 대표하는 자수 예술이다. 레프카라 마을의 레이스 제작 전통은 14세기까지 올라간다. 토착 공예, 1489년에 섬을 지배한 베네치아 궁정인의 자수, 고대 그리스와 비잔틴의 기하 문양이 모두 영향을 주었고, 모든 도안은 네 가지 기본 요소를 조합해 손으로 만든다. 헴스티치, 컷워크, 새틴 스티치 채움, 니들포인트 가장자리 장식이다.

이 기술은 지금도 마을 여성의 주된 생업이다. 여성들은 좁은 골목이나 지붕이 있는 마당에 함께 앉아 이야기를 나누면서 식탁보, 냅킨, 전시용 작품을 만든다. 어린 여자아이는 여러 해 동안 곁에서 보고 익히다가 어머니나 할머니에게 아마천에 무명실을 놓는 법을 정식으로 배운다. 기술을 온전히 익힌 장인은 전통과 자기 개성을 함께 담은 도안을 짓는다. 레이스 제작은 레프카라 여성의 일상 중심에 있고, 정체성을 나타내는 자랑스러운 상징이다.

"레프카리티카"는 2009년에 인류무형문화유산 대표목록에 등재되었다. 레프카라 시의 문화유산 기록보관소, 키프로스 학술연구센터의 구전 전통 기록보관소, 국가유산목록에 모두 기록되어 있다.

판텔리스는 레프카라에서 작은 기념품 가게를 한다. 할머니에게 정사각형 "레프카리티카"를 많이 물려받아 가게 창고에 보관하려고 한다. 창고가 넉넉하지 않아서 일부는 다른 작품 위에 올려야 한다. 판텔리스는 한 번에 몇 개를 놓을 수 있는지 알고 싶다.

창고 바닥은 정수 좌표를 가진 $W \times L$개의 격자점이다. $x$번째 열, $y$번째 행에 있는 점을 $(x, y)$로 쓰고, $1 \le x \le W$, $1 \le y \le L$이다. 이 점 중 일부의 바로 위에 전구가 매달려 있다.

작품을 놓는 규칙은 다음과 같다.

• 작품은 정사각형이고 변은 좌표축과 평행하다. 모든 정수 변 길이가 있고 개수 제한은 없다. 가장 작은 작품의 변은 1이다.
• 변이 $k$인 작품은 왼쪽 위 꼭짓점을 격자점 $(x, y)$에 맞춰 놓으며, 이때 $x \le a \le x + k$, $y \le b \le y + k$인 모든 점 $(a, b)$를 덮는다.
• 작품은 창고 안에 완전히 들어가야 하므로 $x + k \le W$, $y + k \le L$이다. 전구가 허락하면 가장 큰 작품이 창고 전체를 덮을 수도 있다.
• 전구가 매달린 점은 어떤 작품도 덮지 못한다. 경계에 놓인 점도 마찬가지다. 덮으면 레이스가 상한다.
• 큰 작품을 먼저 놓는다. 작품끼리 겹쳐도 되고, 더 작은 작품이 큰 작품 위에 올라가 그 작품을 완전히 덮어도 된다.
• 크기가 정확히 같은 다른 작품을 완전히 덮는 작품은 놓을 수 없다. 즉 변 길이가 같은 두 작품을 같은 점에 놓지 못한다.

아래 그림은 $W = 4$, $L = 3$인 창고를 격자점으로 나타낸 것이다. 전구가 있는 점은 O, 빈 점은 작은 점으로 그렸다. 전구는 $(2, 2)$와 $(3, 3)$에 있다.

여기서는 작품을 하나만 놓을 수 있다. 왼쪽 위 꼭짓점이 $(3, 1)$인 변 1의 작품이다. 다른 자리에 놓으면 전구 아래의 점을 덮게 된다.

• 첫째 줄에 창고 바닥의 너비와 길이를 격자점 개수로 나타낸 두 정수 $W$와 $L$이 주어진다 ($1 \le W, L \le 2000$).
• 둘째 줄에 전구의 개수 $B$가 주어진다 ($0 \le B \le W \times L$).
• 다음 $B$개 줄에는 각각 $i$번째 전구의 좌표 $x_i$와 $y_i$가 주어진다 ($1 \le x_i \le W$, $1 \le y_i \le L$). 같은 점에 전구가 두 개 매달린 경우는 없다.

창고에 한 번에 놓을 수 있는 작품의 최대 개수를 한 줄에 출력한다. 답은 32비트 정수의 범위를 넘을 수 있다.

첫 번째 예제의 창고는 $W = 4$, $L = 5$이고 전구는 $(1, 4)$, $(1, 5)$, $(4, 1)$에 있다. 변이 2인 작품 세 개를 그림 3처럼 놓을 수 있다. 변이 1인 작품은 변이 2인 작품 위에는 올릴 수 있지만 변이 1인 다른 작품 위에는 올릴 수 없어서, 그림 4처럼 아홉 개를 더 놓는다. 모두 열두 개다.