eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Кризис

Кризис

Лимит времени 1 секунда
Лимит использования памяти 256 MiB

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

Пётр

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

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

Входные данные

Первая строка содержит два целых числа N (1 N 50000) - длительность кризисы в днях и S (1 S 100000) - сумма начальных сбережений Петра. Последующие N строк содержат по два натуральных числа, не превышающих 1000000:

  1. Первое число - количество олимпов, за которые в этот день можна было приобрести один галлакт.

  2. Второе число - количество олимпов, которые можно получить, продав один галлакт в этот день. Второе число не превышает первое.

Выходные данные

Вывести одно целое число - наибольшую сумму денег в олимпах, которую мог бы иметь Пётр по окончанию последнего дня кризиса. Гарантируется, що ответ на каждый из тестов жюрі не будет превышать 10^18.

Пример

Входные данные #1
3 1000
100 99
110 105
90 80
Выходные данные #1
1050
Автор Шамиль Ягияев, Даниил Нейтер
Источник 2010 XXIII Всеукраинская олимпиада по информатике, Киев, Март 22 - 26, тур 2