농부 창호는 자신이 키우는 소들을 먹이기 위한 H(1≤H≤50,000)kg의 건초 더미가 필요하다.

총 N(1≤N≤100)명의 건초더미 공급자가 존재하며 편의상 각각 1 부터 N으로 번호를 붙인다.

i번 공급자는 건초를 하나의 패키지로 공급하는데 하나의 패키지는 P_i(1≤P_i≤5,000)㎏의 건초를 C_i(1≤C_i≤5,000)원에 판매를 하는 패키지이다.

i번 공급자는 i번 패키지를 무한정 가지고 있다고 하고 패키지를 살 경우 패키지를 나눠서 사는 경우는 불가능하다.

H㎏이상의 건초를 산다고 했을 때 창호가 지불해야 하는 최소 비용을 출력하는 프로그램을 작성하라.

건초사기 timer 1s memory - MB

건초사기 1s - MB