Problem Statement

A new shop will open tomorrow in the town where yuki lives.
yuki has decided to visit the shop every day starting tomorrow and to collect all of its items by buying one item per day ($1$ item every $1$ day).
Since yuki is the only resident of the town, no one else ever buys the shop's items.

The shop sells $N$ items, and the price of the $i$-th item is initially $A_i$ yen.
However, the price of each item rises by $B_i$ yen every $1$ day.
That is, buying item $i$ on day $d$ after the opening costs $A_i+B_i \times d$ yen.
The opening day itself is regarded as day $0$ after the opening.
Also, each item has only $1$ unit in stock, and the same item cannot be bought $2$ times.

The shop runs a campaign on days when the number of days elapsed since the opening is odd (days $1$, $3$, $5$, ... after the opening).
A person who buys an item on a campaign day may, in addition to the purchased item, buy exactly $1$ other item of their choice for $0$ yen, regardless of its price.

yuki wants to collect all the items in the shop for as little money as possible by choosing the order of purchases wisely.
Find the minimum amount of money required to collect all $N$ items.

Input

$N$
$A_1\ B_1$
$A_2\ B_2$
$.$
$.$
$A_N\ B_N$

The $1$st line gives the number of items $N$.
The following $N$ lines, starting from the $2$nd line, give the information about the items.
Among them, the $i$-th line gives the initial price $A_i$ of item $i$ and the integer $B_i$, separated by a space.

Constraints

• $1 \le N \le 2000$
• $1 \le A_i,B_i \le 10^5\ (i=1, 2, \dots, N)$
• All inputs are integers.

Output

Output the minimum amount of money required to collect the $N$ items. Print a newline at the end.

Sample

3
6 8
2 9
4 7

13

2
6 2
3 3

11

8
3 13
18 8
3 14
1 18
3 3
18 12
10 18
15 19

169