eolymp
bolt
Try our new interface for solving problems
Məsələlər

Mərasim cədvəli

Mərasim cədvəli

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Siz yenicə pulunuz çatmadığı üçün ödəyə bilmədiyiniz hesab almısınız. Təəssüf ki, bu birinci dəfə baş vermir və indi siz pul çatışmazlığını tədqiq etmək qərarına gəldiniz. Səbəb tamamılə aydındır: pulunuzun əksəriyyəti kütləvi yerlərdə mərasimlərə girişlərdə itir.

Siz problemin rast gəldiyi yerdə, elə mərasimin özündə həll edilməsini düşünürsünüz. Siz mərasim büdcəsinə məhdudiyyət qoyursunuz və bu məhdudiyyətdən istifadə etməklə maksimum zövq almaq istəyirsiniz.

Siz əvvəlcədən hər bir mərasimin giriş qiymətini bilərək orada nə qədər zövq ala biləcəyinizi qiymətləndirirsiniz. Siyahı asanlıqla tərtib olunmuşdur, lakin siz büdcəni aşmadan əsasən daha çox zövq ala biləcəyiniz mərasimləri necə saxlayacaqsınız?

Daha çox zövq ala biləcəyiniz optimal mərasimlər çoxluğunu tapan proqramı tərtib edin. Nəzərə alın ki, sizin büdcəniz sona qədər xərclənməyə bilər. Maksimum zövq alın və lazım olandan artıq pul xərcləməyin.

Giriş verilənləri

Giriş verilənlərinin birinci sətri sizin mərasim büdcəsini və mərasimlərin sayını təyin edir. Növbəti n sətrin hər biri iki ədəd ehtiva edir. Birinci ədəd hər bir mərasimin giriş haqqını təyin edir. Mərasimlərin qiyməti 5-25 frank arasıdır. İkinci ədəd 0-dan 10-a qədər tam ədədlə ifadə olunmuş hər bir mərasimin əyləncə sayını təyin edir. Büdcə 500-ü aşmamlıdır və mərasimlərin sayı ən çox 100 ola bilər. Ədədlər bir-birindən boşluqla ayrılmışdır.

Çıxış verilənləri

Hər bir test halı üçün sizin proqram giriş haqlarının cəmini və bütün əyləncə qiymətlərinin cəminin optimal həllini verməlidir. Hər iki ədəd yeganə boşluqla ayrılmalıdır.

Nümunə

Giriş verilənləri #1
50 10
12 3
15 8
16 9
16 6
10 2
21 9
18 4
12 4
17 8
18 9
50 10
13 8
19 10
16 8
12 9
10 2
12 8
13 5
15 5
11 7
16 2
0 0
Çıxış verilənləri #1
49 26
48 32