Годинник | |
|
HIGHWAY
|
| Задача Автомагистраль (HIGHWAY)
Господин Бизнесюк собирается в деловую поездку из родной Логарифмической области страны Олимпия в далекий город Экспоненциальск, причем ехать он будет собственным Мерседесом. Автомагистраль, соединяющая Логарифмическую область с Экспоненциальском, состоит из N последовательных фрагментов. Внутри каждого фрагмента можно ехать или по бесплатной дороге, тратя ai секунд, или по платной, тратя ci олимпийских центов и bi секунд. Между этими фрагментами имеются транспортные развязки, через которые можно переехать с одной дороги на другую. Такие перемещения требуют qi секунд (без разницы, с платной дороги на бесплатную или с бесплатной на платную). При продолжении движения по той же дороге таких задержек не возникает. Начать и завершить движение можно как по платной так и по бесплатной дороге, поэтому развязки есть только между первым и вторым, вторым и третьим, ..., (N-1)-м и N-м фрагментами.Господин Бизнесюк давно знает лозунг «время – деньги» и на данный момент оценивает одну секунду своего времени в K олимпийских центов, а поэтому г. Бизнесюка интересует минимизация величины P + K • T, где P – общая сумма уплаченных дорожных сборов, T – общие затраченное время, смысл величины K пояснено в предыдущем предложении.
Формат ввода/вывода:
Программа HIGHWAY считывает с клавиатуры в первой строке два целых числа N (2 ≤ N ≤ 60) и K (0 ≤ K ≤ 2012). Далее во второй строке считывается три целых числа a1, b1 и c1 – время движения по бесплатной и платной дорогам первого фрагмента и цена проезда по платной дороге. В каждой из следующих N-1 строк считывается по четыре целые числа qi, ai, bi и ci – время на перемещение между дорогами, время движения по бесплатной и платной дорогах этого фрагмента и цена проезда по платной дороге соответственно. Все значения ai, bi и ci (1 ≤ i ≤ N) в пределах от 1 до 1012. Все значения qi (2≤i ≤N) в пределах от 0 до 109.
Пример:
| Ввод |
Вывод |
| 5 7795 17 100004 41 17 10003 23 17 1002 17 17 101 15 17 1 |
13892 |
Пояснение: Для данного примера, минимум величины P + 77T достигается при P = 1110, T = 166 на маршруте «бесплатная (время 95), смена дороги (время 4), платная (время 17, плата 1000), платная (время 17, плата 100), платная (время 17, плата 10), смена дороги (время 1), бесплатная (время 15)».
|
|
|
