3921: 张老师的机器人plus
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
众所周知，张老师最近很喜欢玩他的机器人
而今天张老师给机器人进行了一些改动，支持了转身功能！
现在机器人不但可以勇往直前！还可以急流勇退！（所以还是不支持转向功能)
为了方便描述，我们可以认为机器人可以行动的路线是一条直线，一开始机器人所在位置的坐标是 $0$，每向前走一步坐标 $+1$，向后走一步坐标 $-1$，每走一步就需要花费 $1$ 格电量
现在张老师依旧在路径上设置了 $n$ 个充电宝，第 $i$ 个充电宝所在位置的坐标是 $a_i$，电量是 $b_i$，当机器人到达坐标 $a_i$ 时可以选择是否拿起这个充电宝
这一次张老师给机器人安排的工作是：取得 **所有充电宝** 并 **返回起点**
但是张老师给机器人进行了限制：
1. 中途不得使用充电宝给自己充电
2. 必须先拿低电量的充电宝，再拿高电量的充电宝（即如果存在电量为 $1$ 的充电宝，就必须拿完所有电量为 $1$ 的充电宝以后才能拿电量为 $2$ 的充电宝）
现在张老师想知道，一开始至少给机器人充几格电，才能支撑它拿完所有的充电宝并返回起点？
P.S. 假设机器人电池电量无上限，且拿的下所有的充电宝
输入
输入第一行是两个整数 $n$，表示充电宝数量
接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，用于描述第 $i$ 个充电宝
对于 $20\%$ 的数据，保证 $1 \leq n,|a_i| \leq 10$
对于 $50\%$ 的数据，保证 $1 \leq n \leq 5000, |a_i| \leq 10000$
对于 $100\%$ 的数据，保证 $1 \leq n \leq 100000, |a_i| \leq 10^6$
对于所有数据保证 $a_i \ne a_j \ne 0, 1 \leq b_i \leq n$
接下来 $n$ 行，每行包含两个整数 $a_i,b_i$，用于描述第 $i$ 个充电宝
对于 $50\%$ 的数据，保证 $1 \leq n \leq 5000, |a_i| \leq 10000$
对于 $100\%$ 的数据，保证 $1 \leq n \leq 100000, |a_i| \leq 10^6$
对于所有数据保证 $a_i \ne a_j \ne 0, 1 \leq b_i \leq n$
输出
输出一行包含一个整数，表示张老师一开始至少要给机器人充的电量
样例输入 复制
5
2 2
3 1
1 3
4 2
5 3样例输出 复制
12提示
### 样例解释1
机器人的一种移动路径为：$0 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 1 \rightarrow 0$
### 样例解释2
机器人的一种移动路径为：$0 \rightarrow -5 \rightarrow 4\rightarrow 5\rightarrow -4\rightarrow -3\rightarrow -2\rightarrow 0$
机器人的一种移动路径为：$0 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 1 \rightarrow 0$
机器人的一种移动路径为：$0 \rightarrow -5 \rightarrow 4\rightarrow 5\rightarrow -4\rightarrow -3\rightarrow -2\rightarrow 0$