Farmer John sta esaurendo le scorte e deve acquistare $H$ $(1 \le H \le 50,000)$ libbre di fieno per le sue mucche.

Conosce $N$ $(1 \le N \le 100)$ fornitori di fieno, comodamente numerati $1,\ldots,N$. Il fornitore $i$ vende pacchi contenenti $P_{i}$ $(1 \le P_{i} \le 5,000)$ libbre di fieno al prezzo di $C_{i}$ $(1 \le C_{i} \le 5,000)$ dollari. Ogni fornitore ha una quantità illimitata di pacchi disponibili, e i pacchi devono essere acquistati interi.

Aiutate FJ a trovare il costo minimo necessario per acquistare almeno $H$ libbre di fieno.

Input

• Riga 1: due interi $N$ e $H$, separati da uno spazio.
• Righe $2,\ldots,N+1$: la riga $i+1$ contiene due interi $P_{i}$ e $C_{i}$, separati da uno spazio.

Output

• Riga 1: un intero che rappresenta il costo minimo che FJ deve pagare per ottenere almeno $H$ libbre di fieno.

Esempi

Input 1

2 15
3 2
5 3

Output 1

9

Nota

FJ può acquistare tre pacchi dal secondo fornitore per un costo totale di 9.

Autore del problema: Neal Wu, 2007