Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Очистка террасы

(Время: 1 сек. Память: 16 Мб Сложность: 15%)

«Упади семь раз и восемь раз поднимись»
(с) Японская мудрость

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

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

  1. Повернуться на 90 влево и потратить a единиц энергии.
  2. Повернуться на 90 вправо и потратить b единиц энергии.
  3. Переместиться в клетку, находящуюся перед ним (не выходя при этом за границы террасы), и потратить c единиц энергии.

Если робот-пылесос находится на какой-либо плитке, то он ее отчищает, не тратя энергию. При этом пылесос может несколько раз посещать одну и ту же плитку. Он автоматически отключается, как только отчищает последнюю загрязнённую плитку. Так как дядюшка Поликарп очень любит экономить во всём, но сам не способен рассчитать минимально возможную энергию, нужную для очистки всей террасы, он просит это сделать вас.

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

Входной файл INPUT.TXT содержит пять целых чисел n, m, a, b и c (1 ≤ n, m ≤ 106; 0 ≤ a, b, c ≤ 106).

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

В выходной файл OUTPUT.TXT выведите одно число — ответ на поставленную задачу, выраженный в единицах энергии из условия.

Примеры

INPUT.TXTOUTPUT.TXT
12 3 1 2 17
23 3 2 2 116

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 A. Переполох у турникетов
 B. Поездка в кино
 C. Баобаб
 D. Очистка террасы
 E. Битва школ
 F. Этажи
 G. Космическое сновидение
 H. Неумолкающий Янпул
 I. ЦПСП
 J. Стреляй!
 K. Отряд Стёпы
 L. Swap optimization

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru