Как проиграть контест
Гена - гений спортивного программирования. Он может решить любую задачу, поэтому еще ни разу не проигрывал контесты. Сегодня Гена решил специально плохо написать контест, потому что ему надоело всегда занимать первое место.
Но Гена не может просто не сдавать задачи на контесте, так как это могут назвать неспортивным поведением. Поэтому он решил выбрать неудачную стратегию решения задач, а именно, он хочет сдавать задачи таким образом, чтобы набрать как можно меньше баллов.
Контест состоит из n задач, пронумерованных от 1 до n. За решение задачи i участник получает p[i] баллов. Гена прочитал все задачи и для каждой сразу придумал решение. Также для каждой задачи он оценил время, которое потребуется ему для написания решения для этой задачи: назадачу i Гене потребуется t[i] минут. Осталось выбрать порядок, в котором он будет писать решения. Посмотрев на часы, Гена понял, что до конца контеста осталось t минут.
Гена планирует действовать следующим образом. Он выбирает одну из ранее не решенных задач и пишет её решение за соответствующее время. Гена никогда не выбирает задачу, которую он не сможет написать до конца контеста. После написания решения он сразу отправляет задачу на проверку и получает за нее p[i] баллов. На отправку и проверку решения время не тратится. После этого он переходит к другой задаче. Как только Гена понимает, что он не успеет написать ни одну из оставшихся задач до конца контеста, он перестает писать решения.
Теперь Гена хочет выбрать такой порядок написания задач, который минимизирует его суммарный балл за контест. Помогите Гене определить, какой минимальный возможный суммарный балл он сможет набрать, действуя описанным образом.
Входные данные
Первая строка содержит два числа n и t (1 ≤ n, t ≤ 2000) - количество задач и время до конца контеста в минутах.
Следующие n строк описывают задачи, i-я строка содержит два числа t[i], p[i] (1 ≤ t[i] ≤ 2000, 1 ≤ p[i] ≤ 10^6) - время, необходимое Гене для написания решения для этой задачи, и количество баллов, которое получает участник за решение этой задачи.
Выходные данные
Выведите одно число - минимальное количество баллов, которое Гена может получить на контесте.