Алібаба#3351
Алібаба, улюблений герой наших дитячих казок, прагне стати безсмертним, щоб і надалі дарувати радість дітям. Для досягнення цього він має довести, що здатен на неймовірні вчинки. Є скарбів (n \le 10000), кожен з яких розташований у різних місцях уздовж прямої дороги. Кожен скарб має свій дедлайн, після якого він зникає. Алібаба повинен зібрати всі скарбів, і зробити це якомога швидше. Тому йому потрібно визначити оптимальний порядок, у якому він збиратиме скарби, щоб встигнути до їхніх дедлайнів, починаючи з найбільш вигідної позиції. Алібаба має список місць і дедлайнів для кожного скарбу. Місце знаходиться на відстані d_i від крайньої лівої точки дороги. Час, необхідний для збирання скарбу, вважається миттєвим.
Алібаба повинен визначити найменший час, за який він може зібрати всі скарби.
Кожен набір даних у вхідних даних відповідає певному набору скарбів. Для кожного набору вхідні дані містять кількість скарбів і список пар "місце - дедлайн" у порядку зростання розташувань. Пробіли можуть вільно зустрічатися між числами у вхідних даних. Вхідні дані є коректними.
Для кожного набору даних програма виводить результат у стандартний вихід на окремому рядку. Рішення представляється найменшим часом, за який Алібаба може зібрати всі скарби до їх зникнення. Якщо це неможливо, то виводиться "No solution".
Приклад 1