Годинник | |
|
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)».
|
|
|
