Tô màu

Cho bảng thước \(n \times n\), các hàng được đánh số từ \(1\) đến \(n\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(n\) từ trái sang phải. Ô nằm giao của hàng \(i\), cột \(j\) được gọi là ô \((i, j)\). Trên bảng có \(s\) ô màu đen cần được tô lại thành màu trắng bằng các thao tác có dạng như sau: Chọn một hình chữ nhật có ô trái trên là \((x, y)\) và ô phải dưới là ô \((u, v)\), khi đó toàn bộ các ô trong hình chữ nhật được tô màu trắng với chi phí \(f_{k}(u-x+1, v-y+1)\).

Cho biết, \(f_{1}(a, b)=\min (a, b)\), còn \(f_{2}(a, b)=\max (a, b)\).

Yêu cầu: Cho \(k\) và bảng thước \(n \times n\), hãy tính chi phí nhỏ nhất để đưa tất cả các ô đen thành ô trắng.

Input

• Dòng đầu chứa ba số \(k, n, s\ (n \leq 50)\).
• Tiếp theo là \(s\) dòng, mỗi dòng chứa hai số \(i, j\) mô tả ô màu đen.

Output

• Gồm một dòng chứa một số là chi phí ít nhất.

Example

1 3 4
1 1
1 3
3 1
3 3

2

2 3 4
1 1
1 3
3 1
3 3

3

Scoring

• Subtask \(1\): \(k=1\).
• Subtask \(2\): \(k=2\).