10. Тортики и роботы

Роботы Варя, Гоша и Лёша совместно организовали производство тортиков. Робот Варя генерировала размеры сторон тортика в вареметрах (обозначим их А и В), выпекала тортик и наносила на его поверхность разметку-сетку на квадратные вареметры. Робот Гоша генерировал случайное число N и размещал на торте в случайно выбранных квадратах 2^N кремовых розочек (не более одной на квадратик).

А робот Лёша выполнял интеллектуальную работу: резал торт. Запрограммирован он был так, что каждым разрезом рассекал торт или кусок торта на две части с одинаковым количеством розочек. Размер частей при этом мог быть неодинаковым, а разрезы были прямые и шли строго по разметке. Каждый торт Лёша старался разрезать на максимальное количество кусков, следуя при этом правилам.

Разработайте программу, определяющую, на сколько кусочков Лёша сможет разрезать торт заданного размера и с заданным расположением розочек.

Входные данные. В одной строке через пробел - натуральные A, B и N. А и В в пределах сотни, а N такое, что 2^N розочек на торте помещаются. Далее следуют 2^N строк, в каждой координаты розочки (смотрите на рисунок и читайте пример - разберётесь). Розочки на торте не упорядочены.

Выходные данные. Одно натуральное число - максимальное количество кусков, которое может обеспечить Лёша. Если Лёше не удастся сделать ни одного разреза - ну, торт будет одним большим куском.

Пример. На картинке два торта. Данные, описывающие первый торт, жёлтенький, могут выглядеть так:
4 3 2
1 0
2 0
2 1
2 2
Этот торт Лёша сможет разрезать на 4 куска: сначала он сделает разрез, обозначенный красным, а затем верхний кусок разрежет по вертикали, а нижний по горизонтали. А вот розовый торт Лёша разрезать не сможет, поэтому он останется единым куском.