Контестdə necə uduzmaq olar
Gena idman proqramlaşdırma üzrə bir dahidir. O, hər hansı bir tapşırığı həll edə bilir və buna görə də indiyə qədər heç bir müsabiqədə uduzmayıb. Lakin bu gün Gena, həmişə birinci olmaqdan yorulduğu üçün, müsabiqəni qəsdən pis yazmağa qərar verib.
Gena müsabiqədə sadəcə tapşırıqları təhvil verməməzlik edə bilməz, çünki bu, qeyri-idman davranışı kimi qəbul edilə bilər. Buna görə də, o, mümkün qədər az xal toplamaq üçün uğursuz bir strategiya seçərək tapşırıqları həll etməyə qərar verib.
Müsabiqə n tapşırıqdan ibarətdir və bu tapşırıqlar 1-dən n-ə qədər nömrələnib. Tapşırıq i-ni həll edən iştirakçı p[i] xal qazanır. Gena bütün tapşırıqları oxuyub və hər biri üçün dərhal həll tapıb. Həmçinin, hər bir tapşırıq üçün o, bu tapşırığın həlli üçün nə qədər vaxt lazım olacağını qiymətləndirib: tapşırıq i üçün Genaya t[i] dəqiqə lazımdır. İndi isə o, tapşırıqları hansı ardıcıllıqla yazacağını seçməlidir. Saatına baxaraq, Gena müsabiqənin sonuna qədər t dəqiqə vaxt qaldığını anlayır.
Gena belə bir plan qurub: O, hələ həll edilməmiş tapşırıqlardan birini seçir və müvafiq vaxt ərzində onun həllini yazır. Gena heç vaxt müsabiqənin sonuna qədər yaza bilməyəcəyi bir tapşırığı seçmir. Həll yazıldıqdan sonra o, dərhal tapşırığı yoxlamağa göndərir və bunun üçün p[i] xal alır. Göndərmə və yoxlama üçün vaxt sərf olunmur. Daha sonra o, başqa bir tapşırığa keçir. Gena başa düşəndə ki, qalan tapşırıqlardan heç birini müsabiqənin sonuna qədər yaza bilməyəcək, o, həll yazmağı dayandırır.
İndi Gena tapşırıqları elə bir ardıcıllıqla yazmaq istəyir ki, müsabiqədə ümumi xalı minimum olsun. Gena'ya bu strategiya ilə əldə edə biləcəyi minimum mümkün ümumi xalı müəyyən etməyə kömək edin.
Giriş məlumatları
Birinci sətir iki ədəd n və t (1 ≤ n, t ≤ 2000) - tapşırıqların sayı və müsabiqənin sonuna qədər qalan dəqiqələrdə vaxtı göstərir.
Növbəti n sətir tapşırıqları təsvir edir, i-ci sətir iki ədəd t[i], p[i] (1 ≤ t[i] ≤ 2000, 1 ≤ p[i] ≤ 10^6) - Gena'nın bu tapşırığı həll etmək üçün sərf edəcəyi vaxt və iştirakçının bu tapşırığı həll etdiyi üçün alacağı xal sayını göstərir.
Çıxış məlumatları
Bir ədəd çıxarın - Gena'nın müsabiqədə əldə edə biləcəyi minimum xal sayı.