URI Online Judge | 1851

How To Train Your Dragon

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

After his dragon Smaug failing in the mission of taking care of Erebor, Sauron has become very upset, and his Eye started to look everywhere for a professional dragon trainer, so his other dragons would not fail in their missions. This way Sauron knew Daenerys Targaryen. Impressed by her reputation, Sauron hired her immediately.

Sauron sends dragons to Daenerys almost daily. Some dragons take more time to be trained, others less, and she always trains one dragon at a time, never more than one in a same day, until it is ready to be returned to Sauron. During the days in which Daenerys applies herself to the training of a dragon, she leaves the other dragons sent by Sauron hibernating in a lodging until it is the turn of each one of them. But Sauron's character, although of remarkable perseverance, is not famous by his patience. For each day a dragon of his spends sleeping in the lodging, Sauron, whose Eye sees easily everything which is passed at Daenerys's domains, charges a fine from her, whose value can vary from dragon to dragon, depending on the plans that Sauron has to his dragons. Sauron sends exactly one dragon per day, and the dragon always arrives right in the beginning of the day, so Daenerys can start to train it immediately. Furthermore, if there are dragons sleeping in the lodging and none of them is being trained, Sauron sends a Nazgûl to kill Daenerys.

Daenerys Targaryen wants to minimise the total fine to pay to Sauron and is asking your help. You have already told her that you cannot foresee the future and the best you can do is: whenever she is not working with a dragon and wants to choose one of the lodging to start to train it, you can tell her which dragon to pick up so the choice would be optimal if no more dragons come in the days following.


The i-th line of input refers to a dragon sent by Sauron to Daenerys and consists of two integers: Ti e Fi (1 ≤ Ti, Fi ≤ 103), representing respectively the number of days needed to train the i-th dragon and the fine charged per day that the dragon spends sleeping. For any distinct i and j, Ti / FiTj / Fj. The input has at most 105 lines and ends in end of file.


Output a line containing singly the total value of the fine that Daenerys will pay to Sauron if she follows your advices.

Input Sample Output Sample

4 1
3 4
1 1000
2 2
5 6