İşə qəbul

"'markdown Sizə tikinti layihəsi üçün işçilər işə götürmək lazımdır. İşə qəbul üçün $n$ namizəd müraciət edib və onlar $1$-dən $n$-ə qədər nömrələnib. Hər bir $k$ nömrəli namizəd, işə qəbul edildiyi halda, ona ən azı $S_k$ dollar ödənilməsini tələb edir. Həmçinin, hər bir $k$ nömrəli namizədin ixtisas səviyyəsi $Q_k$ məlumdur. Tikinti fəaliyyəti qaydalarına əsasən, işçilərə ixtisas səviyyələrinə uyğun olaraq nisbətən ödəniş etməlisiniz. Məsələn, əgər siz $Q_A=3\ast Q_B$ olan iki işçi $A$ və $B$ işə götürsəniz, o zaman işçi $A$-ya işçi $B$-yə ödədiyiniz məbləğin üç qatını ödəməlisiniz. Sizə işçilərə tam olmayan məbləğdə pul ödəməyə icazə verilir. Hətta sonlu sayda onluq rəqəmlərlə yazıla bilməyən məbləğlər, məsələn: üçdə bir və ya altıda bir dollar ödəməyə də icazə verilir.

Sizin $w$ dollarınız var və siz mümkün qədər çox işçi işə götürmək istəyirsiniz. Siz kimin işə götürüləcəyinə və onlara nə qədər ödəniləcəyinə qərar verirsiniz, lakin həm işçilərin minimum ödəniş tələblərini, həm də tikinti fəaliyyəti qaydalarını təmin etməlisiniz. Siz $w$ dollar büdcəsinə sığmalısınız.

Bu tikinti layihəsi üçün işçilərin ixtisas səviyyəsi əhəmiyyət kəsb etmir. Siz yalnız ixtisas səviyyəsindən asılı olmayaraq mümkün qədər çox işçi işə götürməkdə maraqlısınız. Lakin, əgər məqsədə çatmaq üçün bir neçə yol varsa, o zaman işçilərə ödəyəcəyiniz ümumi məbləğin mümkün qədər az olacağı birini seçmək istəyirsiniz. Əgər bunu da bir neçə yolla əldə etmək mümkündürsə, bu yollar arasında fərq yoxdur və sizi hər hansı biri qane edəcək.

Namizədlərin minimum ödəniş tələbləri və ixtisas səviyyələri, eləcə də sizin malik olduğunuz pul miqdarı verilmişdir. Bu verilənlər əsasında hansı namizədləri işə götürməli olduğunuzu müəyyən edən proqram yazın. Siz mümkün qədər çoxunu işə götürməli və tikinti fəaliyyəti qaydalarına riayət edərək mümkün qədər az pul xərcləməlisiniz.

Giriş verilənləri

Birinci sətir iki tam ədəd $n$ $(1\le n\le 500000)$ və $w$ $(1\le w\le 10^{10})$ ehtiva edir, boşluqla ayrılmışdır. Növbəti $n$ sətir namizədləri təsvir edir, hər bir sətir bir namizədi təsvir edir. $k$-cı sətir $k$ nömrəli namizədi təsvir edir və iki tam ədəd $S_k$ və $Q_k$ $(1\le S_k,Q_k\le 20000)$ ehtiva edir, boşluqla ayrılmışdır.

Maksimum $w$ dəyəri 32-bitlik məlumat tipində təqdim edilə bilər. Siz $w$ dəyərini bir dəyişəndə saxlamaq üçün long long C/C++ və ya int64 Pascal kimi 64-bitlik məlumat tipindən istifadə etməlisiniz. Əlavə təfərrüatlar texniki məlumat səhifələrində verilmişdir.

Çıxış verilənləri

Birinci sətir $h$ - işə götürdüyünüz işçilərin sayını ehtiva edən bir tam ədəd olmalıdır. Növbəti $h$ sətir işə götürmək üçün seçdiyiniz namizədlərin nömrələrini (fərqli tam ədədlər $1$-dən $n$-ə qədər) təsadüfi qaydada ehtiva etməlidir, hər biri bir sətirdə. "'

Nümunələr