eolymp
bolt
Try our new interface for solving problems
Məsələlər

Шоколадка

Шоколадка

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Команда "Отбой" участвует в очередном марафоне "Угадай мелодию. Rock version". Чтобы было чем подкрепится во время игры, команда взяла с собой большую прямоугольную плитку шоколада размерами w×h. У команды есть список из n пар чисел - размеры шоколадок, которые команда считает счастливыми. Прежде чем приступить к поеданию шоколадки участники команды решили поделить имеющуюся плитку на счастливые шоколадки. Для этого они действуют следующим образом: сначала плитка шоколада ломается на 2 части по линии строго параллельной одной из своих сторон, после чего каждую из полученных частей они могут продолжить ломать аналогичным образом.

Вам поручили определить, какое максимальное количество счастливых шоколадок команда может получить, действуя по заданной схеме. Шоколадки, полученные поворотом счастливых, счастливыми не являются.

Giriş verilənləri

В первой строке входного файла заданы три целых числа w, h, n - размеры плитки шоколадки и количество вариантов размера счастливых шоколадок соответственно (1w, h300, 1nw×h). В следующих n строках заданы пары целых чисел w_i, h_i - размеры счастливых шоколадок (1w_iw, 1h_ih).

Çıxış verilənləri

В единственную строку выходного файла выведите максимальное количество счастливых шоколадок, на которые можно разрезать данную плитку.

Nümunə

Giriş verilənləri #1
21 11 4
10 4
6 2
7 5
15 10
Çıxış verilənləri #1
15