Blobs` Sərgisi
Blobs, Çiçək Şəhərindən tanınmış bir rəssam, yerli incəsənət qalereyasında solo sərgi keçirməyə hazırlaşır. O, sərgilənmək üçün k əsər təqdim edib, lakin təəssüf ki, qalereyada yalnız n sərgi yeri mövcuddur. Hər bir sərgi yeri divara quraşdırılmış rəsm tutucusudur. Hazırlıq zamanı məlum oldu ki, tutucular müxtəlif çəkili rəsmlər üçün nəzərdə tutulub. i-ci tutucu ən çox d_i qram ağırlığında bir sərgini daşıya bilər. Bütün əsərləri nümayiş etdirmək mümkün olmadığından, Blobs hər bir rəsm əsərinin bədii dəyərini a_i olaraq qiymətləndirdi. O, həmçinin onların çəkilərini bilmək üçün hamısını çəkdi və çəkilər w_i (qramla) oldu. Blobs-a sərgilənəcək rəsmlər dəstini seçməkdə kömək edin ki, ümumi bədii dəyəri maksimuma çatdırsın.
Maksimum ümumi bədii dəyərə malik rəsmlər dəstini mövcud sərgi yerlərinə uyğunlaşdıracaq bir proqram yazın. Bir neçə optimal həll mövcuddursa, onlardan hər hansı biri düzgün qəbul ediləcəkdir.
Giriş verilənləri
Giriş faylının birinci sətri iki boşluqla ayrılmış tam ədəd n və k (1 ≤ n ≤ k ≤ 10000) ehtiva edir. İkinci sətir tutucular üçün maksimum yükləri təsvir edən n boşluqla ayrılmış tam ədəd ehtiva edir: d_1, d_2, d_3, … d_n. Sonra k sətir gəlir, hər biri iki boşluqla ayrılmış rəqəm: a_j və w_j, j-ci rəsm əsərinin bədii dəyəri və çəkisi. Rəsmlər nömrələrin artan sırasına görə siyahıya alınır: girişin üçüncü sətri a_1, w_1, dördüncü – a_2, w_2, beşinci – a_3, w_3 və s. ehtiva edir (1 ≤ a_i, d_j, w_j ≤ 1000000, 1 ≤ i ≤ n, 1 ≤ j ≤ k).
Çıxış verilənləri
Çıxış faylı n boşluqla ayrılmış tam ədəd ehtiva etməlidir — müvafiq sərgi yerlərində yerləşdiriləcək rəsmlərin nömrələri. Burada, i mövqeyindəki rəqəm sərgi yerində nümayiş olunacaq rəsm əsərinin nömrəsidir. Əgər sərgi yeri boşdursa, müvafiq mövqedə 0 çıxarın.