Шоколадка#4148
Команда "Відбій" бере участь у черговому марафоні "Відгадай мелодію. Rock version". Щоб було чим підкріпитися під час гри, команда взяла з собою велику прямокутну плитку шоколаду розмірами w \times h. У команди є список з пар чисел — розміри шоколадок, які команда вважає щасливими. Перед тим як приступити до поїдання шоколадки, учасники команди вирішили поділити наявну плитку на щасливі шоколадки. Для цього вони діють наступним чином: спочатку плитка шоколаду ламається на частини по лінії, строго паралельній одній зі своїх сторін, після чого кожну з отриманих частин вони можуть продовжити ламати аналогічним чином.
Вам доручили визначити, яку максимальну кількість щасливих шоколадок команда зможе отримати, діючи за заданою схемою. Шоколадки, отримані поворотом щасливих, щасливими не вважаються.
У першому рядку вхідного файлу задано три цілих числа , , — розміри плитки шоколадки та кількість варіантів розміру щасливих шоколадок відповідно (1 \leq w, h \leq 300, 1 \leq n \leq w \times h). У наступних рядках задано пари цілих чисел w_i, h_i — розміри щасливих шоколадок (1 \leq w_i \leq w, 1 \leq h_i \leq h).
У єдиний рядок вихідного файлу виведіть максимальну кількість щасливих шоколадок, на які можна розламати задану плитку.
Приклад 1