题目描述

农民约翰去砍了一些木头，像往常一样，留下N（2≤N≤100000）头牛吃草。当他回来时，他惊恐地发现，那群奶牛正在他的花园里吃他美丽的花朵。为了最大限度地减少随后的损失，FJ决定立即采取行动，将每头牛运回自己的谷仓。

每头牛i的位置距离其自己的畜棚Ti分钟（1≤Ti≤2000000）。此外，在等待运输时，她每分钟销毁Di（1≤Di≤100）朵花。无论他多么努力，FJ一次只能把一头牛运回她的谷仓。将奶牛i移到谷仓需要2×Ti分钟（Ti到达那里，Ti返回）。FJ从花丛开始，把奶牛运到谷仓，然后走回花丛，不需要额外的时间就可以找到下一头需要运输的奶牛。

编写一个程序来确定FJ应该按照什么顺序来接奶牛，这样就可以最大限度地减少被破坏的花朵总数。

输入格式

第一行一个整数N。

接下来N行，每行两个整数Ti和Di。

输出格式

一个整数，表示最少被破坏的花朵总数。

6
3 1
2 5
2 3
3 2
4 1
1 6

86

提示

约翰按以下顺序返回奶牛：6、2、3、4、1、5。当他把6头牛运到谷仓时，其他人毁坏了24朵花；接下来，他将带走2号奶牛，再失去28个美丽的植物群。对于3、4、1头奶牛，他分别损失了16、12和6朵花。当他带走第5头牛时，没有更多的奶牛破坏花朵，所以这头牛的损失为零。这样损失的花朵总数为24+28+16+12+6=86。