题目描述

河边草原上，无数只羊正在吃草。

突然，N 只狼闯进了羊群。它们开始疯狂地吃羊。假设狼的编号为 1 ~ N，编号为 i 的狼每个单位时间会吃掉 Si 只羊。

你要把狼都抓住并送到河对岸去。河上只有一条船，每次你只能送一只狼到对岸。你抓住一只狼不需要花时间，但你把狼送到河对岸需要时间。你把编号为 i 的狼送到对岸需要 Ti 个单位时间。由于你还要乘船回来，所以你对付编号为 i 的狼实际需要花费的时间是 2·Ti 个单位时间。从你抓住一只狼的那一刻开始，它就没法再吃羊了。

你当然希望被狼吃掉的羊越少越好。聪明的你，很快就想到了一种抓狼顺序，使得从你抓住第一只狼开始，到你抓住最后一只狼结束，中间这段时间，被吃掉的羊的数量最少。

请你输出这个最小值。

输入

第一行：包含一个整数 N

接下来 N 行：每行包含两个整数 Ti, Si

输出

一个整数，表示答案

样例输入

3
2 1
2 5
10 3

样例输出

28

样例解释

首先抓住编号为 2 的狼，来回一共需要花费 2×2=4 个单位时间，另两只狼这段时间会吃掉 (1+3)×4=16 只羊。

然后抓住编号为 1 的狼，来回一共需要花费 2×2=4 个单位时间，另一只狼这段时间会吃掉 3×4=12 只羊。

最后抓住编号为 3 的狼。

中间一共被吃掉 16+12=28 只羊。

数据范围

30% 的数据：1 ≤ N ≤ 10

60% 的数据：1 ≤ N ≤ 20

80% 的数据：1 ≤ N ≤ 5000

100% 的数据：1 ≤ N ≤ 100000, 2 ≤ Ti ≤ 10^6, 1 ≤ Si ≤ 100