Nhà điêu khắc chuẩn bị xây một tượng đài, để thực hiện điều này, ông cần những tấm đá cẩm thạch hình chữ nhật có kích thước W₁, H₁; W₂, H₂; ...; Wₙ, Hₙ. Gần đây, ông ấy nhận được một tấm đá tự nhiên hình chữ nhật lớn. Ông muốn cắt tấm đá này thành các tấm có kích thước mong muốn.

Bất kỳ mảnh đá tự nhiên nào (tấm đá ban đầu hoặc các tấm cắt từ nó) đều có thể được cắt theo chiều ngang hoặc chiều dọc thành hai tấm hình chữ nhật với chiều rộng và chiều cao là các số nguyên, cắt xuyên qua mảnh đá đó. Đây là cách duy nhất để cắt các mảnh và các mảnh không thể ghép lại với nhau. Vì đá tự nhiên có hoa văn trên đó nên các tấm không thể xoay: nếu nhà điêu khắc cắt một tấm có kích thước A × B thì nó không thể được sử dụng làm tấm có kích thước B × A trừ khi A = B. Ông có thể tạo ra không hoặc nhiều tấm với kích thước mong muốn. Một tấm đá bị lãng phí nếu nó không có kích thước mong muốn nào sau khi tất cả các vết cắt được hoàn thành.

Nhà điêu khắc tự hỏi làm thế nào để cắt tấm đá ban đầu sao cho lãng phí ít đá nhất có thể. Ví dụ, hãy giả sử trong hình dưới đây, chiều rộng của tấm đá ban đầu là 21 và chiều cao của tấm đá ban đầu là 11, và kích thước mong muốn của các tấm là 10 × 4; 6 × 2; 7 × 5 và 15 × 10. Diện tích lãng phí tối thiểu có thể là 10, và hình vẽ cho thấy một chuỗi vết cắt với tổng diện tích lãng phí là 10.

Nhiệm vụ của bạn: Viết một chương trình tính toán tổng diện tích tối thiểu của tấm đá ban đầu phải bị lãng phí, cho kích thước của tấm đá ban đầu và kích thước mong muốn của các tấm.

Đầu vào:

• Dòng đầu tiên của đầu vào chứa hai số nguyên: số đầu tiên là W, chiều rộng của tấm đá ban đầu, và sau đó là H, chiều cao của tấm đá ban đầu.
• Dòng thứ hai chứa một số nguyên N: số lượng kích thước tấm mong muốn. Các dòng N tiếp theo chứa kích thước mong muốn của các tấm. Mỗi dòng trong số này chứa hai số nguyên: số đầu tiên là chiều rộng Wi và sau đó là chiều cao Hi của kích thước tấm mong muốn đó (1 ≤ i ≤ N).

Đầu ra:

Hãy viết trên một dòng một số nguyên duy nhất: tổng diện tích tối thiểu của tấm đá ban đầu phải bị lãng phí.

Sample Input 1

21 11
4
10 4
6 2
7 5
15 10

Sample Output 1

10