On April 20^th, 1945, a certain megalomaniacal dictator left his bunker to spend his 56^th birthday decorating a group of youth soldiers. It would be his last trip to the surface from his underground bunker.

Before privately conceding defeat in his underground Berlin bunker on the 22^nd, a desperate dictator plays out a final battle simulation. In this simulation, a fleet of airborne carryalls is set to attack the prospering metropolis, «bobhob314 Town». In «bobhob314 Town», town blocks are arranged according to an infinite number line, each labelled by an integer accordingly.

There are ~N~ ~(1 \le N \le 500)~ carryalls, each of which can carry any number of carryalls. All of the carryalls start in block ~0~. Carryalls can be freely attached to or detached from other carryalls when they are not in flight. Any number of attacks may be carried out with these carryalls. A single attack begins with flying a carryall (say, the ~i^\text{th}~ one) with any attached carryalls a distance of ~d_i~ ~(1 \le d_i \le 10^9)~ kilometres in a single direction (left or right). Specifically, an attack from block ~k~ has a carryall ~i~ flying to either block ~(k-d_i)~ or block ~(k+d_i)~. Then, just before landing, the carryall attacks the landing block. Initially, none of the carryalls are functional. To get the ~i^\text{th}~ carryall in the air, ~c_i~ ~(1 \le c_i \le 10^5)~ Reichsmark must be spent.

You are the enemy economics leader of the «bobhob314 Town Defense Armada», and you are asked with determining the least amount of money needed to attack all of your beloved hometown's blocks in order to circumvent these dastardly plans.

Constraints

Subtask 1 [40%]

~1 \le N \le 10~

Subtask 2 [60%]

No additional constraints.

Input Specification

Line ~1~: ~N~

Lines ~2~ to ~N+1~: Two space-separated integers. On the ~i^\text{th}~ line, these will be ~d_i~ and ~c_i~, respectively.

Output Specification

The minimum cost needed to attack all of «bobhob314 Town»'s blocks. If it is not possible to bomb all of the blocks, output Hooray!

Sample Input

2
8 4
1 3

Sample Output

3