Yetenek Gösterisi#10389
Farmer John, kolaylık olmak amacıyla 'den 'e kadar numaralandırılmış ineğini, yıllık sığır yetenek gösterisine katılmak üzere ilçe fuarına getiriyor! . ineğin w_i ağırlığı ve t_i yetenek seviyesi vardır, bunların ikisi de tam sayıdır.
Varışta, Farmer John bu yılki yetenek gösterisinin yeni kurallarına oldukça şaşırır:
Gösteriye katılan inek grubunun toplam ağırlığı en az olmalıdır (böylece sadece güçlü bireyler değil, güçlü inek takımlarının yarışması sağlanır).
Toplam yeteneğin toplam ağırlığa oranı en büyük olan grup kazanır.
FJ, tüm ineklerinin birlikte en az ağırlığında olduğunu gözlemler, bu yüzden her zaman ilk kuralı sağlayan bir takım oluşturabilir. Böyle bir takımla elde edebileceği en iyi yetenek/ağırlık oranını belirlemesine yardım edin.
İlk satır iki tam sayı içerir: ve W~(1 \le n \le 250, 1 \le W \le 1000). Sonraki satırın her biri bir ineği tanımlar ve iki tam sayı içerir: w_i ve t_i~(1 \le w_i \le 10^6, 1 \le t_i \le 1000).
, Farmer John'un toplam ağırlığı en az olan bir inek grubuyla elde edebileceği en büyük yetenek/ağırlık oranı olsun. değerini, yani değerinin aşağı yuvarlanmış tam sayı halini yazdırın.
Örnek 1
Bu örnekte, genel olarak en iyi yetenek-ağırlık oranı, sadece yeteneği ve ağırlığı olan inek kullanılarak elde edilirdi. Ancak, toplam ağırlık en az olması gerektiğinden, en uygun çözüm bu ineği yeteneği ve ağırlığı olan inekle birlikte kullanmaktır. Bu, (11 + 21) / (10 + 20) = 32 / 30 = 1.0666\ldots yetenek-ağırlık oranını verir; bu değer ile çarpılıp aşağı yuvarlandığında sonucunu verir.