Дистанционный практикум по программированию

Маленькая девочка Лада любит играть с пони и программировать. Особенно играть с пони.

У Лады есть карта Эквестрии (сказочной страны, где живут пони) размером N * M, разбитая на квадраты единичной длины. Также у Лады есть N * M карточек, каждая из которых может закрыть ровно один единичный квадрат. Карточки бывают двух типов. На карточках первого типа нарисован лес, а на карточках второго типа нарисованы полянки. Карточек первого типа у Лады ровно K штук. Лада может раскладывать карточки по карте Эквестрии в произвольном порядке так, чтобы каждый единичный квадрат накрывала ровно одна карточка.

После раскладывания карточек Лада хочет поместить на карту свою любимую пони Пинки Пай. Её пони занимает квадрат 2 * 2 на карте Эквестрии. Лада также хочет, чтобы клетки, на которых стоит Пинки Пай, были только одного типа (или только лес, или только полянки). Для каждого возможного расположения карточек Лада может сосчитать, сколько вариантов расположения пони есть на карте. Чем больше таких вариантов расположения пони, тем больше расположение карточек на карте нравится Ладе. Ладе очень хочется узнать, сколько максимум вариантов расположения пони на карте она может получить, раскладывая карточки.

Поскольку Лада еще маленькая, ей очень трудно сделать это самой, поэтому она просит помощи у вас.

Формат входных данных                                          

В единственной строке задано три числа N, M и K - размеры Эквестрии и количество карточек с лесом у Лады.

Формат выходных данных

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

 

 

Примеры

input	output
2 2 4	1
2 2 3	0

 

Описание подгрупп тестов

№ группы	Ограничения	Количество баллов
1	0 <= N, M <= 3000, один из типов карточек отсутствует	5
2	0 <= N, M <= 3000, карточек одного из типов  не больше трёх	10
3	0 <= N, M <= 3000, ширина или длина карты равна двум	15
4	0 <= N, M <= 5	20
5	N, M >= 1, N * M <= 150, K <= 150	50