Буст для популярного поста

У школьного медиа есть пост, который нужно удержать в «популярном» ровно c часов подряд.

Продвижение можно покупать двумя способами:

• на 1 час за a монет;
• пакетом на 7 часов за b монет.

Пакеты можно покупать сколько угодно. Если продвижения куплено больше, чем нужно, лишние часы просто «сгорают» — это разрешено.

Найдите минимальное количество монет, которое придётся потратить.

Формат ввода

В одной строке даны три целых числа a, b, c.

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

Выведите одно целое число — минимальную стоимость.

Ограничения

• 0 ≤ a ≤ 700000000
• 0 ≤ b ≤ 700000000
• 0 ≤ c ≤ 700000000

Пример

Ввод:

3 10 8

Вывод:

13

Ключевое наблюдение: покупка продвижения — это сумма независимых «кусочков» по времени. Для каждых 7 часов не важно, что происходит в других местах: вы просто решаете, оплатить их пакетом за b или семью часами по a. То же самое с остатком (меньше 7 часов): его можно добрать по 1 часу или одним лишним пакетом, а лишние часы сгорят.

Почему жадно работает: стоимость линейная, ограничения на число покупок нет, а «сгорание» разрешено. Значит, оптимум получается из локальных минимальных выборов для каждого блока.

План:

• Найдите q, r = divmod(c, 7), где q — число полных блоков по 7 часов, r — остаток.
• Для каждого полного блока выберите дешевле: пакет или 7 одиночных часов: min(b, 7*a).
• Полные блоки стоят q * min(b, 7*a).
• Остаток r часов: либо r*a, либо один пакет b (лишнее сгорит), берём min(r*a, b).
• Ответ — сумма двух частей.

Сложность: O(1) по времени и памяти.

Частая ошибка: считать, что пакет на 7 часов можно брать только для «полных» семёрок. На самом деле для остатка тоже нужно сравнить с b, потому что переплата может быть выгоднее, чем докупать по 1 часу.