Паша сильно увлекся криптовалютами. Недавно он наткнулся на альткоины — очередную криптовалюту.
Сейчас у Паши S рублей. Сегодня начинаются торги альткоинами, они будут длиться n дней. Каждый день торгов Паша может либо купить сколько-то альткоинов, либо продать какое-то количество альткоинов из тех, которые у него есть, либо ничего не делать. В i-й день можно купить один альткоин за ai рублей или продать один альткоин за bi рублей.
Какое максимальное количество рублей может оказаться у Паши под конец торгов?
Формат входных данных В первой строке вводятся два целых числа n и S (1≤n≤50000,1≤S≤1000000) — продолжительность торгов в днях и кол-во рублей у Паши в начале торгов соответственно.
Последующие N строк содержат информацию о каждем дне торгов. В i-й из этих строк вводятся два целых числа ai и bi (1≤bi≤ai≤1000000) — цена покупки и продажи альткоина соответственно.
Формат выходных данных Выведите максимальное количество рублей, которое может оказаться у Паши под конец торгов.
входные данные
3 1000
100 99
110 105
90 80
выходные данные
1050
входные данные
3 15
4 3
9 4
9 8
выходные данные
27
Пытался решить под конкретные примеры, но дальше ответы неверные WA. Какие примеры могут быть?
n, s = map(int, input().split())
delcount = 0
buy = []
sell = []
buycount = 0
for i in range(n):
a, b = map(int, input().split())
buy.append(a)
sell.append(b)
for i in range(n):
if buy.index(min(buy)) > sell.index(max(sell)):
buy.remove(min(buy))
delcount += 1
else:
buycount = s // min(buy)
s -= (s // min(buy)) * min(buy)
s += buycount * max(sell)
break
print(s)