ТПУ: основной тур

Соревнование завершилось 15.04.18 в 16:00

H. Поиск предателя

Ограничение по времени: 2 с.
Ограничение по памяти: 256 МБ

Паша готовит олимпиады по программированию с командой из n человек (не считая самого Пашу). Недавно выяснилось, что кто-то из этой команды предательски передает идеи задач другим авторским коллективам. Паша точно знает, что из n человек ровно один является предателем, он хочет любой ценой выяснить, кто же.

У Паши есть k идей задач. До начала подготовки важнейшей олимпиады осталось m дней и необходимо установить предателя за это время. В начале каждого из m дней Паша может рассказать каждому члену команды определённое подмножество имеющихся у него идей задач (в том числе может рассказать все идеи, а может — ни одной). В конце каждого дня Паша может проверить через предателей других авторских коллективов какие задачи оказались у них на тренировках и увидеть, какие из его идей, рассказанных утром этого же дня, ушли конкурентам.

Паша хочет гарантированно узнать за m оставшихся дней, кто же является предателем. Более того, он хочет оставить неизвестными конкурентам как можно больше из имеющихся у него идей задач. Напишите программу, которая определит, можно ли выявить предателя в таких условиях и, если да, какое наибольшее количество идей Паше удастся гарантированно не отдать конкурентам.

Входные данные

Единственная строка входных данных содержит три целых положительных числа n, k и m — количество человек, работающих над задачами с Пашей, количество имеющихся у Паши идей и количество дней на поиск предателя соответственно (1 \leqslant n \leqslant 10^{5}, 1 \leqslant m, k \leqslant 10).

Выходные данные

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

Примеры
Стандартный вводСтандартный вывод
1212 8 24
5 2 1-1