题目描述

小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“信息与未来”夏令营选拔赛）

来源

市赛