Farmer John manque de provisions et doit acheter $H$ $(1 \le H \le 50,000)$ livres de foin pour ses vaches.

Il connaît $N$ $(1 \le N \le 100)$ fournisseurs de foin, numérotés pour plus de commodité $1,\ldots,N$. Le fournisseur $i$ vend des paquets contenant $P_{i}$ $(1 \le P_{i} \le 5,000)$ livres de foin au prix de $C_{i}$ $(1 \le C_{i} \le 5,000)$ dollars. Chaque fournisseur dispose d’un nombre illimité de paquets, qui doivent être achetés entiers.

Aidez FJ à trouver le coût minimal pour acheter au moins $H$ livres de foin.

Entrée

• Ligne 1 : deux entiers $N$ et $H$, séparés par un espace.
• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient deux entiers $P_{i}$ et $C_{i}$, séparés par un espace.

Sortie

• Ligne 1 : un entier représentant le coût minimal que FJ doit payer pour obtenir au moins $H$ livres de foin.

Exemples

Entrée 1

2 15
3 2
5 3

Sortie 1

9

Remarque

FJ peut acheter trois paquets au deuxième fournisseur pour un coût total de 9.

Auteur du problème : Neal Wu, 2007