Farmer John emmène $N$ vaches numérotées $1\ldots N$ au concours annuel de talents bovins de la foire du comté. La vache $i$ a un poids entier $w_i$ et un talent entier $t_i$.

Les nouvelles règles le surprennent :

(i) Le groupe doit peser au moins $W$, pour faire concourir des équipes fortes plutôt que seulement des individus forts.

(ii) Le groupe au rapport talent total sur poids total maximal gagne.

Toutes ses vaches pèsent au moins $W$ ensemble, donc (i) est réalisable. Trouvez le meilleur rapport pour une telle équipe.

Entrée

La première ligne contient $N$ ($1 \leq N \leq 250$) et $W$ ($1 \leq W \leq 1000$). Les $N$ lignes suivantes donnent les entiers $w_i$ ($1 \leq w_i \leq 10^6$) et $t_i$ ($1 \leq t_i \leq 10^3$).

Sortie

Trouvez le meilleur rapport avec un poids au moins $W$. Si la réponse est $A$, affichez la partie entière inférieure de $1000A$ pour produire un entier. Elle supprime la partie fractionnaire d’un nombre non entier en l’arrondissant vers le bas.

Exemples

Entrée 1

3 15
20 21
10 11
30 31

Sortie 1

1066

Remarque

La vache de talent 11 et poids 10 donne le meilleur rapport seule, mais il faut 15 de poids : on ajoute celle de talent 21 et poids 20. $(11+21)/(10+20)=32/30=1.0666666...$, multiplié par 1000 et arrondi vers le bas, donne 1066.

Auteur du problème : Brian Dean