Сайт підготовки до олімпіади з інформатики

Криза

(XXIII Всеукраїнська олімпіада з інформатики, другий тур)

«Знав би прикуп, жив би в Ялті»

Петро

Внаслідок кризи курс національної валюти планети Олімпія (олімп) почав коливатися відносно міжгалактичної валюти (галакт). Після закінчення кризи, Петро – один з мешканців планети – вирішив підрахувати, скільки він міг би заробити, маючи початкові заощадження, якщо б наперед знав щоденний курс.

Завдання Напишіть програму CRISIS, що за інформацією про суму заощаджень Петра на момент початку кризи в олімпах та коливання курсу олімпів відносно галактів визначить максимальну кількість грошей, яку Петро міг би мати на кінець кризи. Неможна покупати та продавати нецілу кількість галактів. На кінець кризи усі гроші повинні бути переведені в олімпи.

Вхідні дані Перший рядок вхідного файлу CRISIS.DAT містить два цілих числа N (1≤N≤50 000) – довжина кризи у днях та S (1≤S≤100 000) – сума початкових заощаджень Петра. Наступні N рядків містять по два натуральних числа, які не перевищують 1 000 000:

1.     Перше число – кількість олімпів, за які у цей день можна було придбати один галакт.

2.     Друге – кількість олімпів, які можна отримати, продавши один галакт цього дня. Друге число не перевищує перше.

Вихідні дані Єдиний рядок вихідного файлу CRISIS.SOL має містити одне ціле число – найбільшу суму грошей в олімпах, яку міг би мати Петро по закінченню останнього дня кризи. Гарантовано, що відповідь на кожен з тестів журі не буде перевищувати 10¹⁸.

Оцінювання Щонайменше у 25% тестів буде виконуватись додаткове обмеження N≤20.

Щонайменше у 75% тестів буде виконуватись додаткове обмеження N≤2000.

Приклад вхідних та вихідних даних