Spettacolo dei Talenti#10389
Farmer John sta portando le sue mucche, comodamente numerate da a , alla fiera della contea per competere nell'annuale spettacolo dei talenti bovini! La sua -esima mucca ha peso w_i e livello di talento t_i, entrambi numeri interi.
Al suo arrivo, Farmer John rimane piuttosto sorpreso dalle nuove regole dello spettacolo dei talenti di quest'anno:
Il gruppo di mucche iscritte allo spettacolo deve avere un peso totale di almeno (per garantire che competano squadre forti di mucche, e non solo individui forti).
Il gruppo con il rapporto più alto tra talento totale e peso totale vince.
FJ osserva che tutte le sue mucche insieme pesano almeno , quindi può sempre iscrivere una squadra che soddisfi la prima regola. Aiutalo a determinare il miglior rapporto tra talento e peso che può ottenere con una tale squadra.
La prima riga contiene due interi e W~(1 \le n \le 250, 1 \le W \le 1000). Ciascuna delle successive righe descrive una mucca e contiene due interi w_i e t_i~(1 \le w_i \le 10^6, 1 \le t_i \le 1000).
Sia il più grande rapporto possibile tra talento totale e peso totale che Farmer John può ottenere con un gruppo di mucche di peso totale almeno . Stampa , cioè il valore arrotondato per difetto a un intero.
Esempio 1
In questo esempio, il miglior rapporto talento-peso complessivo si otterrebbe utilizzando solo la mucca con talento e peso . Tuttavia, poiché il peso totale deve essere almeno , la soluzione ottimale consiste nell'utilizzare questa mucca insieme alla mucca con talento e peso . Questo dà un rapporto talento-peso di (11 + 21) / (10 + 20) = 32 / 30 = 1.0666\ldots, che, moltiplicato per e arrotondato per difetto, dà .