Задача C. Солнечные батареи

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

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

Отдельные модули этих батарей имеют форму квадрата со стороной 1 метр. Модули можно последовательно соединять с одним или двумя соседними элементами в непрерывный ряд и размещать вдоль прямой линии или под углом 90°. В нижнем правом углу крыши устанавливается аккумулятор А, который будет накапливать электрическую энергию, вырабатываемую солнечными панелями. В нижнем левом углу размещается контроллер К, управляющий процессом заряда аккумулятора.

Необходимо разместить модули на крыше вокруг и между k окон размера a×b метров таким образом, чтобы они не мешали прохождению солнечного света и их общая площадь была максимальна (см. рис.). Расстояние между окнами и от окна до края крыши – 1 метр. В места установки контроллера и аккумулятора модули солнечных батарей не размещаются.

Определите количество n модулей, которые нужно закупить, чтобы смонтировать максимальную по площади систему солнечных батарей на крыше теплицы с k окнами.

Напишите программу для решения этой задачи!

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

Единственная строка содержит три целых числа, каждое из которых отделено друг от другого одним пробелом: a, b, k, где a – ширина окна в метрах, b – длина окна в метрах, k – количество окон на крыше теплицы.

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

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

Ограничения

0 < a ≤ 104

0 < b ≤ 103

0 < k ≤ 102

a > b

Примеры тестов

Стандартный вход Стандартный выход
1

  3 2 5

  38
2

  42 21 16
  

  1082

0.095s 0.017s 17