/ WHOJ / 题库 /

光之国保卫战

光之国保卫战

题目描述

有一群怪兽闯进了光之国疯狂吸收光之能量,奥特之父决定立即把所有的怪兽都赶回各自的怪兽星球。怪兽的编号为 1N(2N100000)1 \sim N(2≤N≤100000),怪兽i要返回自己的星球需要 Ti(2×1000000)T_i(≤2×1000000) 天,而且每停留在光之国一天,它就会吸收 Di(Di100)D_i(D_i≤100) 单位的能量。奥特之父每次只能赶走一头怪兽回自己的星球,来回就需要 2×Ti2×T_i 天的时间。请你帮助奥特之父至少损失多少光之能量才能把所有的怪兽都赶出光之国。

格式

输入格式

第一行为正整数 NN

接下来 NN 行,每行两个整数 TiT_iDiD_i 表示怪兽 ii 的信息。

输出格式

仅一个整数,表示光之国受到的最少损失。

样例1

样例输入1

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

样例输出1

86

来源

地址:Online Judge\text{Online~Judge}
作者:征宇
模拟赛T3T3