Sifariş Bölücü
Elektron mübadilə mürəkkəb real vaxt sifariş emalı sistemidir. Hazırda elektron mübadilələr hər gün bazarda milyonlarla sifarişi idarə edir. Siz müştərilər üçün icra xidmətləri göstərən kiçik bir şirkət qurmusunuz və mübadilələr arasında böyük sifarişlərin bölünməsi problemi ilə qarşılaşırsınız. Yeni bir mübadilə qurmaq çox rəqabətlidir, buna görə də sifarişi bölmək üçün yalnız məhdud sayda mübadilə mövcuddur 1 ≤ N ≤ 30.
Sifarişin nominalı (mübadilələrdə icra olunmalı olan proqnozlaşdırılan məbləğ) 1 ≤ L ≤ 10^9 və qiyməti var. Bu problemin çərçivəsində siz yalnız nominalı düşünürsünüz. Sifarişin mübadiləyə göndərildiyi qiymət müştəri tərəfindən təmin ediləcək və olduğu kimi mübadiləyə ötürüləcək. Verilən sifariş, hər bir 0 ≤ i < N üçün verilmiş R_i nisbətlərinə uyğun olaraq mübadiləyə göndərilən bir neçə uşaq sifarişinə bölünməlidir. Lakin, hər bir mübadilənin addım ölçüsü məhdudiyyətləri var. Hər bir sifariş nominalı mübadilə tərəfindən müəyyən edilmiş addım ölçüsünə bölünməlidir. Sizə hər bir mübadilənin addım ölçüsü S_i verilir, yəni hər bir mübadilə yalnız S_i, 2·S_i, 3·S_i... nominal sifarişləri qəbul edə bilər.
Çünki müştəri sifarişinin nominalını dəqiq şəkildə uşaq sifarişlərinə bölmək həmişə mümkün deyil, ən yaxşı mümkün bölgünü əldə etmək üçün bir alqoritm yazılmalıdır ki, D=|L-C_i| minimallaşdırılsın, burada müvafiq mübadilələrə ayrılmış uşaq sifarişlərinin nominalı C_i kimi göstərilir. Müştərilər uşaq sifariş ölçüsünün CR_i=L·R_i/R_i ilə əhəmiyyətli dərəcədə fərqli olmamasına üstünlük verirlər. Bu tələbi qarşılamaq üçün C_i yalnız CR_i addım ölçüsünə yuvarlanaraq əldə edilə bilər. Lakin, əgər CR_i S_i ilə bölünə bilirsə, tələb olunur ki, C_i = CR_i. Bu o deməkdir ki, əgər göndərilə bilirsə, verilmiş nisbətə uyğun olaraq uşaq sifariş nominalını göndərməlisiniz, əks halda onu ya yuxarı, ya da aşağı yuvarlayın. Əgər aşağı yuvarlama 0 nominal verirsə, o zaman mübadiləyə sifariş göndərməmək seçiminiz var.
Giriş verilənləri
Hər bir test halının ilk sətri 2 tam ədədi ehtiva edir: mübadilələrin sayı 1 ≤ N ≤ 30, bölünəcək sifariş nominalı 1 ≤ L ≤ 10^9. İkinci sətir N tam ədədi ehtiva edir, 0 ≤ R_i ≤ 100, R_i > 0. Üçüncü sətir N tam ədədi ehtiva edir, addım ölçüləri 1 ≤ S_i ≤ 10^9.
Çıxış verilənləri
Hər bir test halı üçün bir sətir çıxarın, uşaq sifarişlərinin cəmi nominalı L_r=C_i, yuxarıda təsvir olunan qaydalara uyğun olaraq optimallaşdırılmış. Əgər bir neçə optimal L_r varsa, daha kiçik dəyəri çıxarın.