1526 - 小X与游戏

题目描述

小X和小Y正在玩一个游戏,这个游戏是这样的:桌上放着 n 叠卡片,每叠恰好有两张。每张卡片有一个分数。小X为先手,双方轮流操作。轮到一方操作时,他可以选择取走某一叠卡片顶端的那一张(即:若这一叠还剩 2 张则取走上面的一张,否则取走下面的一张),并获得它的分数。他也可以选择不取。若卡片取完了、或者双方都选择不取卡片,那么游戏结束。

小X和小Y都希望自己的分数减去对方的分数尽可能大。现在假设小X和小Y都绝顶聪明,总是做出对自己最有利的决策,请算出游戏结束时小X比小Y高多少分。

在任何时刻,同一叠牌的上下两张牌的的大小,小X和小Y都是能看到的

输入

输入的第一行包含一个正整数 n

接下来 n 行,每行包含 2 个用空格隔开的非负整数 a_i, b_i,分别表示第 i 叠中放在上面、下面的卡片的分值。

输出

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

样例

输入

2
1 2
4 3

输出

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

(常州市2017“信息与未来”夏令营选拔赛)

来源

市赛

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 742
通过人数 354
金币数量 3 枚
难度 提高


上一题 下一题