Винни-Пух хочет навестить своего давнего друга — Кролика. У него есть смартчасы, которые выдают ему возможных маршрутов до дома Кролика.
Если Винни пойдет по -му пути, он достигнет дома Кролика через
минут и при этом заплатит
мурлей.
Ваша задача — определить минимальную стоимость пути до дома Кролика, такого, что время движения Пуха при этом будет не более .
Входные данные:
В первой строке входных данных записаны два числа через пробел: и
(
) — количество маршрутов до дома Кролика и максимальное допустимое время пути соответственно.
В каждой из следующих строк записано по два числа в строке:
и
(
) — стоимость в мурлях и длительность пути в минутах
-го пути соответственно.
В качестве ответа запишите результат работы программы для входных данных, представленных в файле file.txt.
Пример входного файла:
Пояснение к примеру:
Если Пух пойдет первым путем, то потратит мурлей. Пойти вторым он не сможет, так как второй путь слишком долгий. Ну а если Винни пойдет по третьему пути, то заплатит всего
мурля. Это и является минимальной стоимостью допустимого пути. Поэтому ответ на данный пример —
.
f = open("file.txt")
n, t = map(int, f.readline().split())
ans = 100000000
for i in range(n):
a, b = map(int, f.readline().split())
if (b <= t):
ans = min(ans, a)
print(ans)