Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00029A

Energija

Manufactering and optimal controlling the energy manufacturing is very important to every society. There is a prediction that Bosnia & Herzegovina will for 10 years from now have thousands of different power plants. People will build parks of new hydro and wind power plants by the existing thermal power plants. Every power plant can work with full capacity and every other capacity that is bigger than zero.
Electrical energy is hard to store so it is needed to manufacture only enough to satisfy the need for it.



Your task is to write a program that will for given electricity demand in one day and for given list of electric power plants with their maximum electrical energy producing and the price of producing find the cheapest manufactering plan.



InputThe first line of standard input contains a number N ( 1 ≤ N ≤ 1000 ) that represents the number of electrical power plants. After that, the next N lines contain two numbers where in the i-th line first number represents the maximum manufactering capacity of a power plant and where the second number represents the price of manufactering of a power plant by one unit of measure from that energy. All numbers are positive integers that are less than 10000000.


OutputThe output contains only one line with the minmal price that satisfies energy producing.



Input
5
21
5 4
7 3
8 5
4 5
1 6
Output
86



Input
3
13
2 1
7 3
8 4
Output
39

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.