Kredit Cədvəli
Şimal Qütbü Çimərlik Bankı, ipoteka müraciətlərinin müəyyən bir dəstini qəbul etmək qərarına gəlməlidir. Hər bir müraciət a∈App qəbul müddəti d_a ilə müəyyən edilir, yəni tələb olunan kredit t_a vaxtında ödənilməlidir, burada 0≤t_a≤d_a. Əgər müraciət qəbul olunarsa, Bank p_a mənfəət əldə edir. Zaman, Bankın bütün App müraciətləri haqqında qərar verdiyi konvensional zaman başlanğıcı 0-dan başlayaraq tam vahidlərdə ölçülür. Bundan əlavə, Bank istənilən vaxt maksimum L kredit ödəyə bilər. Bankın siyasəti yalnız mənfəətə yönəlib: mənfəəti maksimumlaşdıran müraciətlərin S⊆App alt dəstini qəbul edir. Problem, verilmiş ipoteka müraciətləri dəsti App üzrə Bankın əldə edə biləcəyi maksimum mənfəəti hesablamaqdır.
Məsələn, L=1, App={a,b,c,d}, (p_a,d_a)=(4,2), (p_b,d_b)=(1,0), (p_c,d_c)=(2,0), və (p_d,d_d)=(3,1) olduğunu nəzərdən keçirin. Aşağıdakı cədvəl qəbul edilmiş ipoteka müraciətlərinin bütün mümkün dəstlərini və kredit ödənişlərinin cədvəlini göstərir. Ən yüksək mənfəət 9-dur və {c,d,a} dəstinə uyğundur. c müraciəti ilə tələb olunan kredit 0 vaxtında ödənilir, d ilə uyğun gələn kredit 1 vaxtında ödənilir və nəhayət, a krediti 2 vaxtında ödənilir.
Giriş verilənləri
Bir giriş mətn faylından məlumat dəstlərini oxuyan bir proqram yazın. Hər bir məlumat dəsti ipoteka müraciətləri dəstinə uyğundur və iki tam ədədlə başlayır: 0≤N≤10000 dəstdəki müraciətlərin sayını göstərir və 0≤L≤100 Bankın istənilən vaxt ödəyə biləcəyi maksimum kredit sayını göstərir. N cüt tam ədədlər p_i d_i, i=1..N, müraciət i-nin mənfəətini 0≤p_i≤10000 və son tarixini 0≤d_i≤10000 göstərir. Giriş məlumatları boşluqlarla ayrılır, doğrudur və faylın sonu ilə bitir.
Çıxış verilənləri
Hər bir məlumat dəsti üçün proqram qəbul edilmiş ipoteka müraciətlərindən Bankın əldə edə biləcəyi maksimum mənfəəti hesablayır. Nəticə standart çıxışda bir sətirin əvvəlindən çap olunur. Çıxışda boş sətirlər olmamalıdır. Aşağıda giriş/çıxış nümunəsi göstərilmişdir.