题目描述

两个人，面前$N$盘菜，每盘菜两个属性，味道$W_i$，价格$C_i$，两个人轮流选菜。

• 第一个人（先手）贪心的选当前价格最高的，如果价格一样，选味道好的。
• 第二个人（后手）的全局目标是，自己吃到的(味道总和-价格总和)最大。

问：第二个人最终的答案是多少?

输入格式

第一行为一个整数 $N$.

接下来 $N$ 行，每行为两个整数 $W_i,C_i$.

$N\leq5000,1\leq W_i,C_i\leq1e8$

输出格式

一行一个整数，为第二个人最终的答案

4
100 150
125 80
120 70
130 60

120

提示

这是以前的例题，讲太多遍了，所以变成了练习题。