Sara 正在 NCPC (Never Crashing Personal Computers) 进行暑期实习。一天，办公室里出现了一个罕见的生物：一道算法题！

图片由 Umberto 提供，遵循 Unsplash 许可

公司有一台在电路板上放置电子元件的机器。通常情况下，它一次只能放置一个元件。但最近机器进行了一次升级，允许同时放置两个不同的元件。此时，瓶颈变成了放置时间较长的那个元件。现在，机器应该采取什么策略来最小化总放置时间并不显而易见。Sara 决定编写一个算法来确定该策略。

你有 $N$ 种不同的电子元件。第 $i$ 种元件有 $f_i$ 个，且该种元件的放置时间为 $t_i$ 纳秒。目标是通过一系列操作放置所有元件。在一次操作中，机器可以选取类型为 $i$ 和 $j$ 的两个元件（其中 $i \neq j$），并同时放置它们。这需要 $\max(t_i, t_j)$ 纳秒。机器也可以在一次操作中放置单个类型为 $i$ 的元件，这需要 $t_i$ 纳秒。

计算放置所有元件所需的最短总时间。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)。 接下来的 $N$ 行，每行包含两个整数 $f_i$ 和 $t_i$ ($1 \le f_i \le 10^4, 1 \le t_i \le 10^9$)。

输出格式

输出一个整数，表示放置所有元件所需的最短时间。

样例

输入格式 1

3
2 7
2 1
3 10

输出格式 1

31

输入格式 2

3
2 10
2 11
2 12

输出格式 2

35

输入格式 3

4
2 11
7 10
3 5
1 1

输出格式 3

72