Nhà điêu khắc Hy Lạp Phidias đang chuẩn bị xây dựng một công trình mới. Ông cần những tấm đá cẩm thạch hình chữ nhật có kích thước \(W_1\times H_1,W_2\times H_2,\ldots,W_N\times H_N\).

Phidias vừa nhận được một phiến đá hình chữ nhật lớn và muốn cắt nó thành các tấm có kích thước cần dùng. Mỗi lần cắt, ông chọn một miếng đá hiện có rồi cắt thẳng theo chiều ngang hoặc chiều dọc, xuyên suốt miếng đó, để chia nó thành hai hình chữ nhật có chiều rộng và chiều cao nguyên. Đây là cách cắt duy nhất được phép; các miếng đá không thể được ghép lại.

Do hoa văn trên đá, các miếng đá không được xoay: một tấm kích thước \(A\times B\) không thể thay cho tấm \(B\times A\), trừ khi \(A=B\). Với mỗi kích thước cần dùng, Phidias có thể tạo ra không tấm nào hoặc một số lượng tùy ý các tấm.

Sau khi cắt xong, một miếng đá bị bỏ phí nếu kích thước của nó không thuộc các kích thước cần dùng. Hãy tính tổng diện tích bị bỏ phí nhỏ nhất.

Ví dụ, phiến đá ban đầu rộng 21 và cao 11; các kích thước cần dùng là \(10\times4\), \(6\times2\), \(7\times5\) và \(15\times10\). Diện tích bỏ phí nhỏ nhất là 10. Hình dưới minh họa một cách cắt đạt được giá trị đó.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(W,H\): chiều rộng và chiều cao của phiến đá ban đầu.
• Dòng thứ hai chứa số nguyên \(N\), số kích thước cần dùng.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(W_i,H_i\): chiều rộng và chiều cao của kích thước cần dùng thứ \(i\).

Dữ liệu ra

In một số nguyên trên một dòng: tổng diện tích nhỏ nhất của phiến đá ban đầu phải bỏ phí.

Ràng buộc

• \(1\le W,H\le600\).
• \(1\le N\le200\).
• \(1\le W_i\le W\) và \(1\le H_i\le H\) với \(1\le i\le N\).

Phân nhóm

Có 20 bộ kiểm thử, mỗi bộ có số điểm tối đa là 5. Trong 50% số bộ kiểm thử, \(W\le20\), \(H\le20\) và \(N\le5\).

Ví dụ

21 11
4
10 4
6 2
7 5
15 10

10