Як програти контест
Гена — геній спортивного програмування. Він може розв'язати будь-яке завдання, тому ще жодного разу не програвав контести. Сьогодні Гена вирішив навмисно погано виступити на контесті, адже йому набридло завжди займати перше місце.
Однак Гена не може просто не здавати завдання на контесті, оскільки це можуть розцінити як неспортивну поведінку. Тому він вирішив обрати невдалу стратегію розв'язання завдань, а саме, він хоче здавати завдання так, щоб набрати якомога менше балів.
Контест складається з 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) - час, необхідний Гені для написання розв'язання для цього завдання, і кількість балів, яку отримує учасник за розв'язання цього завдання.
Вихідні дані
Виведіть одне число - мінімальну кількість балів, яку Гена може отримати на контесті.