Electronic Components

Interview

Time limit4sMemory limit1024 MB

Summary

Given N component types with counts and placement times, find the minimum total time to place all components when two different types can be placed in one move.

Level: Medium5 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

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 places one component at a time. A recent update lets it place two different components at the same time. The placement takes as long as the slower of the two components, so the bottleneck is the component with the greater placement time. It is not obvious what strategy minimizes the total placement time. Sara decides to write an algorithm to find that strategy.

There are $N$ different types of electronic components. There are $f_i$ copies of the $i$ th type, and each component of this type takes $t_i$ nanoseconds to place. The goal is to place all of the components using a sequence of moves. In one move, the machine can take two components of types $i$ and $j$ , where $i \neq j$ , and place both simultaneously. This takes $\max(t_i, t_j)$ nanoseconds. The machine can also place a single component of type $i$ in one move, which takes $t_i$ nanoseconds.

Calculate the minimum possible time to place all components.

Input

The first line contains the integer $N$ ( $1 \leq N \leq 1000$ ).

Each of the following $N$ lines contains two integers $f_i$ and $t_i$ ( $1 \leq f_i \leq 10^4$ , $1 \leq t_i \leq 10^9$ ).

Output

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

Examples3

Example 1
Input
```
3
2 7
2 1
3 10
```
Expected output
```
31
```
Example 2
Input
```
3
2 10
2 11
2 12
```
Expected output
```
35
```
Example 3
Input
```
4
2 11
7 10
3 5
1 1
```
Expected output
```
72
```