Interview Room of Terror

Interview

Time limit1sMemory limit1024 MB

Summary

Interviews run one at a time. Find the minimum sum of the finish times of all departments, given each department's total interview time.

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

Problem

Employees of the Korea Information Technology Promotion Agency each have a one-on-one interview with the president once every six months.

The agency has $N$ departments. A department can leave work only after every employee in it has finished their interview. Interviews are held one at a time.

Find the minimum possible value of the sum of the times at which all departments leave work.

Input

The first line contains the number of departments $N$ ( $1 \le N \le 1000$ ). The next $N$ lines each contain the number of employees in a department and the interview time per employee, separated by spaces. The total number of employees across all departments is at most $1\,000\,000$ , and the interview time per employee is an integer from $1$ to $1\,000$ minutes.

Output

Print the minimum possible sum of the times at which all departments leave work, in minutes.

Examples1

Example 1
Input
```
3
2 5 50
2 20 10
1 100
```
Expected output
```
300
```