האספקה של Farmer John הולכת ואוזלת, והוא צריך לקנות $H$ $(1 \le H \le 50,000)$ פאונד חציר לפרות שלו.

הוא מכיר $N$ $(1 \le N \le 100)$ ספקי חציר, שמוספרו לשם הנוחות $1,\ldots,N$. ספק $i$ מוכר חבילות המכילות $P_{i}$ $(1 \le P_{i} \le 5,000)$ פאונד חציר במחיר $C_{i}$ $(1 \le C_{i} \le 5,000)$ דולרים. לכל ספק יש מספר בלתי מוגבל של חבילות זמינות, ויש לקנות חבילות שלמות.

עזרו ל־FJ למצוא את העלות המזערית הדרושה לקניית לפחות $H$ פאונד חציר.

קלט

• שורה 1: שני מספרים שלמים $N$ ו־$H$, מופרדים ברווח.
• שורות $2,\ldots,N+1$: שורה $i+1$ מכילה שני מספרים שלמים $P_{i}$ ו־$C_{i}$, מופרדים ברווח.

פלט

• שורה 1: מספר שלם אחד המייצג את העלות המזערית שעל FJ לשלם כדי להשיג לפחות $H$ פאונד חציר.

דוגמאות

קלט 1

2 15
3 2
5 3

פלט 1

9

הערה

FJ יכול לקנות שלוש חבילות מהספק השני בעלות כוללת של 9.

מחבר הבעיה: Neal Wu, 2007