Задача TOWER.
В комп'ютерній грі "Страшна помста 2" головному герою -безстрашному лицарю - потрібно піднятися з
1-го на N-й поверх високої вежі. Вежа має
М драбин, причому k-а драбина веде з a[k]-го на
b[k]-ий поверх (a[k]<b[k]). Герой витрачає
3 секунди на підйом по драбині на один поверх і
5*k+7 секунд на перебіжку від однієї драбини до іншої по
k-ому поверху. На
k-ому поверсі знаходяться
k чаклунів, кожного з яких лицар вбиває за
5 секунд. За який найменьший час
T герой зможе піднятися з першого на
N-ий поверх?
Врахуйте, що лицар може залишити
k-у драбину або стати на неї на будь-якому поверсі між
a[k] і b[k] включно. Герой не витрачає часу на першому та на
N-ому поверхах.
Ви маєте написати програму
TOWER, яка читає вхідні данї з
клавіатури і віводить відповідь на екран.
Формат введення:
N M
a[1] b[1]
a[2] b[2]
...
a[M] b[M]
Формат файла TOWER.SOL:
T
Обмежения:
1<N<1000000;
1<M<5000;
драбини розміщені так, що завжди можливо потрапити на
N-ий поверх.
Приклад:
Введення:
10 5
1 3
6 9
4 8
3 8
5 10
Виведення:
81
В цьому прикладі герою потрібно дістатися на
10-ий поверх вежі. В цій вежі є
5 драбин: перша простягається з
1-го по 3-ій поверх, друга - с
6-го по 9-ий і т.д. Спочатку лицар піднімається
1-ою драбиною на
3-ій поверх, затративши
3*2=6 секунд. Далі він перебирається на
4-у , вбиваючи 3-ох чаклунів за
5*3+7=22 секунди, і поднимається на
5-ий поверх за
3*2=6 секунд. На 5-ому поверсі герой переходить на
5-у драбину за
5*5+7=32 секунди, і, врешті-решт, досягає
10-го поверху за
3*5=15 секунд. Перемога! Затрачено часу:
6+22+6+32+15=81 секунда.