#7182. 【提高】小X与游戏 普及−

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小X和小Y正在玩一个游戏,这个游戏是这样的:桌上放着n叠卡片,每叠恰好有两张。每张卡片有一个分数。小X为先手,双方轮流操作。轮到一方操作时,他可以选择取走某一叠卡片顶端的那一张(即:若这一叠还剩2张则取走上面的一张,否则取走下面的一张),并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片,那么游戏结束。
小X和小Y都希望自己的分数减去对方的分数尽可能大。现在假设小X和小Y都绝顶聪明,总是做出对自己最有利的决策,请算出游戏结束时小X比小Y高多少分。

输入格式

输入的第一行包含一个正整数n。
接下来n行,每行包含2个用空格隔开的非负整数a[i], b[i],分别表示第i叠中放在上面、下面的卡片的分值。

输出格式

输出仅有一行包含一个整数,表示游戏结束时小X比小Y高多少分。如果小X的分数比小Y低则输出一个负数。

样例

样例输入1

2
1 2
4 3

样例输出1

1

数据范围与提示


【样例解释】
小X取走4,小Y取走3,小X不取,小Y不取,游戏结束。4-3=1

【数据范围】
对于30%的数据,1<=n<=1000, b[i]=0
对于70%的数据,1<=n<=1000
对于100%的数据,1<=n<=100000, 0<=a[i], b[i]<=1000000