题目描述

Sara 正在 NCPC（Never Crashing Personal Computers）公司做暑期实习。某天，办公室里出现了一种罕见生物：一道算法题！

公司有一台机器用于把电子元件安装到电路板上。通常它一次只安装一个元件。但最近机器升级了，允许它同时安装两个不同类型的元件。此时耗时由两个元件中安装时间较大的那个决定。因此，要最小化总安装时间，策略就不再显然。Sara 决定写一个算法来确定最优策略。

你有 $N$ 种不同类型的电子元件。第 $i$ 种元件有 $f_i$ 个，每个该类型元件的安装时间为 $t_i$ 纳秒。目标是通过一系列操作安装完所有元件。

一次操作中，机器可以取两个不同类型 $i,j$ 的元件（$i e j$）并同时安装，耗时为 $\max(t_i,t_j)$ 纳秒。机器也可以单独安装一个类型为 $i$ 的元件，耗时为 $t_i$ 纳秒。

请计算安装完所有元件所需的最小总时间。

输入格式

第一行包含整数 $N$。

接下来 $N$ 行，每行包含两个整数 $f_i,t_i$。

$$1\le N\le 1000,\qquad 1\le f_i\le 10^4,\qquad 1\le t_i\le 10^9$$

输出格式

输出一个整数，表示安装所有元件的最小可能时间。

输入输出样例 #1

输入 #1

3
2 7
2 1
3 10

输出 #1

31

输入输出样例 #2

输入 #2

3
2 10
2 11
2 12

输出 #2

35

输入输出样例 #3

输入 #3

4
2 11
7 10
3 5
1 1

输出 #3

72