Farmer John porta $N$ mucche numerate $1\ldots N$ al concorso bovino annuale della fiera della contea. La mucca $i$ ha peso intero $w_i$ e talento intero $t_i$.

Le nuove regole lo sorprendono:

(i) Il gruppo deve pesare almeno $W$, per far gareggiare squadre forti, non solo individui forti.

(ii) Vince il gruppo con il massimo rapporto talento totale su peso totale.

Tutte insieme pesano almeno $W$, quindi (i) è possibile. Trova il massimo rapporto per una squadra simile.

Input

La prima riga contiene $N$ ($1 \leq N \leq 250$), $W$ ($1 \leq W \leq 1000$). Le successive $N$ righe danno interi $w_i$ ($1 \leq w_i \leq 10^6$), $t_i$ ($1 \leq t_i \leq 10^3$).

Output

Trova il massimo rapporto con peso almeno $W$. Se è $A$, stampa il pavimento di $1000A$ per produrre un intero: elimina la parte frazionaria arrotondando in basso se non è già intero.

Esempi

Input 1

3 15
20 21
10 11
30 31

Output 1

1066

Note

Talento 11 e peso 10 sarebbe migliore da sola, ma serve peso 15. Si aggiunge la mucca con talento 21 e peso 20. $(11+21)/(10+20)=32/30=1.0666666...$, per 1000 e arrotondato in basso, dà 1066.

Autore del problema: Brian Dean