Фидий
Известный древнегреческий скульптор Фидий готовится к постройке очередного выдающегося монумента. Для этого ему требуются мраморные прямоугольные плитки заданных размеров 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).
Выходные данные
Выходной файл должен содержать одно целое число – минимальную суммарную площадь неиспользуемых плиток.