Farmer John está ficando sem suprimentos e precisa comprar $H$ $(1 \le H \le 50,000)$ libras de feno para suas vacas.

Ele conhece $N$ $(1 \le N \le 100)$ fornecedores de feno, convenientemente numerados de $1,\ldots,N$. O fornecedor $i$ vende pacotes que contêm $P_{i}$ $(1 \le P_{i} \le 5,000)$ libras de feno ao custo de $C_{i}$ $(1 \le C_{i} \le 5,000)$ dólares. Cada fornecedor tem uma quantidade ilimitada de pacotes disponíveis, e os pacotes devem ser comprados inteiros.

Ajude FJ a encontrar o custo mínimo necessário para comprar pelo menos $H$ libras de feno.

Entrada

• Linha 1: dois inteiros $N$ e $H$, separados por um espaço.
• Linhas $2,\ldots,N+1$: a linha $i+1$ contém dois inteiros $P_{i}$ e $C_{i}$, separados por um espaço.

Saída

• Linha 1: um inteiro que representa o custo mínimo que FJ precisa pagar para obter pelo menos $H$ libras de feno.

Exemplos

Entrada 1

2 15
3 2
5 3

Saída 1

9

Nota

FJ pode comprar três pacotes do segundo fornecedor por um custo total de 9.

Créditos do problema: Neal Wu, 2007