Farmer John kończą się zapasy i musi kupić $H$ $(1 \le H \le 50,000)$ funtów siana dla swoich krów.
Zna $N$ $(1 \le N \le 100)$ dostawców siana, dla wygody ponumerowanych $1,\ldots,N$. Dostawca $i$ sprzedaje paczki zawierające $P_{i}$ $(1 \le P_{i} \le 5,000)$ funtów siana w cenie $C_{i}$ $(1 \le C_{i} \le 5,000)$ dolarów. Każdy dostawca ma nieograniczoną liczbę paczek, a paczki muszą być kupowane w całości.
Pomóż FJ znaleźć najmniejszy koszt zakupu co najmniej $H$ funtów siana.
Wejście
- Wiersz 1: dwie liczby całkowite $N$ i $H$, rozdzielone spacją.
- Wiersze $2,\ldots,N+1$: wiersz $i+1$ zawiera dwie liczby całkowite $P_{i}$ i $C_{i}$, rozdzielone spacją.
Wyjście
- Wiersz 1: jedna liczba całkowita oznaczająca najmniejszy koszt, jaki FJ musi ponieść, aby uzyskać co najmniej $H$ funtów siana.
Przykład
Wejście 1
2 15 3 2 5 3
Wyjście 1
9
Uwagi
FJ może kupić trzy paczki od drugiego dostawcy za łączny koszt 9.
Autor zadania: Neal Wu, 2007