Задача №112521. Фидий
Известный античный скульптор Фидий готовится создать ещё один удивительный монумент. Для этого ему нужны прямоугольные мраморные плитки размеров W 1 × H 1 , W 2 × H 2 , ... , W N × H N . Недавно Фидий получил огромную прямоугольную мраморную плиту. Он хочет разрезать эту плиту, чтобы получить плитки желаемых размеров. Любой кусок мрамора (изначальная плита или любая плитка, вырезанная из неё) можно разрезать горизонтальной или вертикальной прямой на две прямоугольные плитки с целыми шириной и высотой. Разрезать плитки по-другому нельзя, объединять плитки тоже нельзя. Поскольку на мраморе есть узор, плитки нельзя поворачивать: если у Фидия есть плитка размера A × B , он не может использовать её как плитку размера B × A , если A ≠ B . Фидий может сделать ноль или больше плиток каждого из желаемых размеров. После того, как сделаны все разрезы, кусок мрамора выбрасывают, если его размеры не являются какими-то из желаемых. Фидию интересно, как разрезать изначальную плиту так, чтобы пришлось выбрасывать как можно меньше мрамора.
Напишите программу, которая по размерам изначальной плиты и желаемым размерам плиток посчитает минимальную суммарную площадь мрамора, которую придётся выбросить.
Первая строка ввода содержит два целых числа W и H — ширину и высоту изначальной плиты, соответственно ( 1 ≤ W , H ≤ 600 ). Вторая строка содержит единственное целое число N — количество желаемых размеров плиток ( 0 < N ≤ 200 ). Следующие N строк содержат желаемые размеры плиток. В каждой из этих строк содержится по два целых числа W i и H i — ширина и высота желаемого размера соответствующей плитки ( 1 ≤ i ≤ N , 1 ≤ W i ≤ W , 1 ≤ H i ≤ H ). Решения, работающие только для W ≤ 20 , H ≤ 20 и N ≤ 5 , будут оцениваться из 50 баллов.
Вывод должен содержать единственную строку, в которой находится единственное число — минимальная возможная площадь мрамора, который придётся выбросить.
21 11 4 10 4 6 2 7 5 15 10
10