Electronic Components

문제

Sara is doing her summer internship at NCPC (Never Crashing Personal Computers). One day, a rare creature appeared in the office: an algorithmic problem!

The company has a machine that places electronic components on circuit boards. Normally, it would do this one component at a time. But recently the machine has received an update which allows it to place two different components simultaneously. The bottleneck then becomes the component with greater placement time. Now it is far from obvious what strategy the machine should use in order to minimize the total placement time. Sara decides to write an algorithm to determine this strategy.

You have $NN$ different types of electronic components. There are $f_{i}f\_i$ copies of the $ii$th type, and the components of this type have a placement time of $t_{i}t\_i$ nanoseconds. The goal is to place all of the components using a sequence of moves. In one move, the machine can take two components of type $ii$ and $jj$, where $i\mathrm{\ne }ji\; \backslash neq\; j$, and place both of them simultaneously. This takes $\max (t_i,t_j)\backslash max(t\_i,\; t\_j)$ nanoseconds. The machine can also place a single component of type $ii$ in one move, which takes $t_{i}t\_i$ nanoseconds.

Calculate the minimum possible time to place all components.

입력

The first line of input contains the integer $NN$ ($1\le N\le 10001\; \backslash leq\; N\; \backslash leq\; 1000$).

The following $NN$ lines each contain two integers $f_{i}f\_i$ and $t_{i}t\_i$ ($1\le f_i\le {10}^{4}1\; \backslash leq\; f\_i\; \backslash leq\; 10^4$, $1\le t_i\le {10}^{9}1\; \backslash leq\; t\_i\; \backslash leq\; 10^9$).

출력

Print one integer, the minimum time to place all components.

3
2 7
2 1
3 10

31

3
2 10
2 11
2 12

35

4
2 11
7 10
3 5
1 1

72