## Secret Santa

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Fardin is a secret Santa! Every Christmas, Fardin dresses up as a polar bear and spreads his good will to homes which do not have chimneys. He accomplishes this by throwing presents through the windows (sometimes the windows are not open). This Christmas, Fardin comes across a particularly interesting building. Approached from the side, the building has only one column, and is 100 stories tall. There are windows are certain floors, and Fardin has bought specific gifts for each of these floors with windows; each gift is for floor and has a certain weight . Fardin starts on the roof, and with his superhuman strength, can move to one floor up or down every second (from the roof, it takes one second to move to floor 100). Fardin also requires one second to throw a present through a window. Furthermore, every second Fardin's total stress increases by the sum of the gifts that he has not yet delivered, or is currently throwing through a window. Obviously, Fardin does not like to be stressed out while wearing a bear costume hanging from a building, so he asks you to find an order for him to deliver the presents so that he experiences the least stress.

#### Input Specification

Line 1: one integer , the number of presents Fardin must deliver

Next lines: for each line , there contains two integers, and

It is guaranteed that no two presents are for the same floor.

#### Output Specification

Output one integer, the minimum amount of stress Fardin must bear to deliver all the presents. The output is guaranteed to fit in a 32-bit integer.

#### Sample Input

3
100 1
1 200
2 1

#### Sample Output

20505

#### Explanation for Sample Output

There are three presents Fardin must deliver. One must go to floor 100 and has weight 1, one must go to floor 1 and weighs 200, and one must go to floor 2 and weights 1. In the optimal strategy, Fardin goes directly to floor 1, taking 100 seconds, and throws the present through in another second. The total stress delivering the first present is . Next, Fardin moves to floor 2 and throws the present in. This adds stress. Finally, Fardin goes to floor 100 and delivers his last present for more stress. The total stress is .

• commented on Dec. 14, 2015, 5:55 p.m.

every second Fardin’s total stress increases by the sum of the gifts that he has not yet delivered, or is currently throwing through a window

should we assume you mean the sum of the weights of the gifts?

• commented on Dec. 14, 2015, 5:56 p.m.

yes

• commented on Dec. 14, 2015, 5:57 p.m. edit 3

I <3 you Weiwei

that took me way too long to do :(