თივის შესყიდვა

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 128 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2008/09, NOV, SILVER


ფერმერ ჯონს უნდა შეიძინოს მინიმუმ H (1<= H <= 50,000) კილოგრამი თივა. მან იცის  N (1 <= N <= 100 მომწოდებელი, 
რომლებიც გადანომრილია
1-დან N-მდე. i-ური მომწოდებელი ყიდის პაკეტს, რომელიც შეიცავს P_i (1 <= P_i <= 5,000)
კილოგრამ
თივას და მისი ღირებულება არის C_i (1 <= C_i <= 5,000)დოლარი. ყოველ მომწოდებელს აქვს შეუზღუდავი
რაოდენობის პაკეტი.
 შესყიდვა შეიძლება მხოლოდ მთლიანი პაკეტის. ჯონმა უნდა შეიძინოს არანაკლებ H კილოგრამი თივა.
დაეხმაროთ ჯონს, რომ ეს შესყიდვა განახორციელოს მინიმალური ღირებულებით.
 
 
შეტანის ფორმატი:
* ხაზი 1: ორი ჰარით გაყოფილი მთელი: N და H
* ხაზები 2..N+1: ხაზი i+1 ორი ჰარით გაყოფილი მთელი: P_i და C_i
 
 
გამოტანის ფორმატი:
* ხაზი 1: ერთი მთელი - მინიმალური თანხა, რომელიც საჭიროა მინიმუმ H კილოგრამი თივის შესაძენად.
 
 
 



მაგალითები

შესატანი მონაცემები
2 15 3 2 5 3 დაკოპირება
გამოსატანი მონაცემები
9 დაკოპირება

შენიშვნა

გამოტანის დეტალები:
ჯონს შეუძლია იყიდოს სამი პაკეტი მეორე მომწოდებლისაგან, საერთო ღირებულებით 9 დოლარი.