İstedadlar şousu
Con adlı fermer özünün n inəyini, ardıcıl olaraq 1..n nömrələnmiş, inək istedad yarışmasının keçirildiyi yarmarkaya gətirdi. Onun i-ci inəyi w[i] çəkisi və t[i] istedad səviyyəsinə malikdir - hər ikisi tam ədədlərdir.
Con gəldikdən sonra yarışmanın yeni qaydalarına təəccübləndi:
(i) Çəkisi ən az W olan bir inək qrupu iştirak etməlidir.
(ii) İstedadın çəkiyə nisbəti ən yüksək olan qrup qalib gəlir.
Con gördü ki, onun bütün inəkləri birlikdə çəkisi W-dən çoxdur, buna görə də o, asanlıqla (i) şərtini yerinə yetirəcək. Ona istənilən komandası üçün istedadın çəkiyə nisbətinin ən yüksək əmsalını müəyyən etməyə kömək edin.
Giriş Məlumatları
Girişin ilk sətiri n (1 ≤ n ≤ 250) və W (1 ≤ W ≤ 1000) ehtiva edir. Növbəti n sətirin hər biri bir inəyi iki tam ədəd w[i] (1 ≤ w[i] ≤ 10^6) və t[i] (1 ≤ t[i] ≤ 1000) ilə təsvir edir.
Çıxış Məlumatları
Çəkisi W-dən az olmayan Conun qrupları üçün istedadın çəkiyə nisbətinin mümkün olan ən yüksək əmsalını müəyyən edin. Əgər cavabınız A-dırsa, 1000A-nın tam hissəsini çıxış edin ki, cavab tam ədəd olsun. Nəticənin kəsr hissəsi atılır, əgər ədəd tam deyilsə, aşağıya yuvarlaqlaşdırılır.
Nümunə
Bu nümunədə ən yaxşı əmsal 11 istedadı və 10 çəkisi olan bir inək tərəfindən əldə edilir, lakin ən az 15 çəki tələb olunduğundan, məsələnin optimal həlli 10 11 inəyi və 20 21 inəyini istifadə etməkdir. İstedadın çəkiyə nisbəti (11 + 21) / (10 + 20) = 32 / 30 = 1.0666666... olur, bu 1000 ilə vurulur və kəsr hissəsi atıldıqda 1066 alınır.