Фідій
Відомий скульптор стародавньої Греції Фідій готується до побудови чергового видатного монумента. Для цього йому потрібні мармурові прямокутні плитки заданих розмірів W_1_{×}H_1, W_2×H_2, ..., W_N×H_N.
Нещодавно Фідій отримав велику прямокутну мармурову плиту. Він хоче розрізати плиту так, щоб отримати плитки заданих розмірів. Мармурова плита чи плитка може бути розрізана лише вертикальним чи горизонтальним розрізом на дві прямокутні плитки. Розріз здійснюється від краю до краю. Це єдиний спосіб розрізання плит і плиток. Вирізані плитки не можна з'єднувати ніяким способом. Так як мармур має рисунок, плитки не можна обертати. Тобто, якщо Фідій вирізав плитку розміром A×B, вона не може бути використана у якості плитки B×A, крім випадка, коли A = B. Він може вирізати 0 чи більше плиток кожного з потрібних розмірів, і при цьому можуть отриматись плитки інших розмірів, які не будуть використовуватись. Фідій хоче знати, як потрібно розрізати задану плиту, щоб сумарна площа невикористовуваних плиток була мінімальною.
Наприклад, нехайь ширина заданої плити становить 21 і висота дорівнює 11, а задані розміри плиток: 10×4, 6×2,7×5 та 15×10. Тоді мінімально можлива площа невикористовуваних плиток дорівнює 10. Рисунок илюструє один із способів різрізання заданої плити.
Потрібно написати програму, яка за заданими розмірами початкової плити та розмірами потрібних плиток обчислює мінімальну сумарну площу невикористовуваних плиток.
Вхідні дані
У першому рядку вхідного файлу міститься два цілих числа. Перше число W – ширина заданої плити, друге H – висота заданої плити (1 ≤ W ≤ 600, 1 ≤ H ≤ 600). Другий рядок містить одне ціле число N (0 < N ≤ 200) – кількість потрібних розмірів плиток. Наступні N рядків містять потрібні розміри плиток. Кожен з цих рядків містить по два цілих числа: W_i – ширину та H_i – висоту (1 ≤ W_i ≤ W, 1 ≤ H_i ≤ H, 1 ≤ i ≤ N).
Вихідні дані
Вихідний файл повинен містити одне ціле число – мінімальну сумарну площу невикористовуваних плиток.