#2345. 希蒙与蒙蒙选石头

希蒙与蒙蒙选石头

希蒙与蒙蒙选石头

题目背景

蒙蒙经过了一个假期的特训以后,回到了小赛码的基地,她立即拉着希蒙来玩一个游戏...

题目描述

一共有nn堆石头,由希蒙和蒙蒙依次选择,并且由蒙蒙优先选择。

蒙蒙选择第ii堆石头可以得到aia_i分。

希蒙选择第ii堆石头可以得到bib_i分。

每堆石头只能被取一次。

直到最后一堆石头被取完则游戏结束。

两人都想最大化其分数的差值,即假设蒙蒙的分数为score1score_1,而希蒙的分数为score2score_2,对于蒙蒙,她想最大化score1score2score_1-score_2,而对于希蒙,他想最大化score2score1score_2-score_1

两人都绝顶聪明,所以请你输出游戏结束时ans=score1score2ans=score_1-score_2的值。

输入格式

请注意输入文件名。

第一行一个整数nn,表示石头的堆数。

接下来一共nn行,每行两个整数aia_ibib_i,含义见上。

输出格式

请注意输出文件名。

你一共需要输出一个整数ansans,含义见上。

样例 #1

样例输入 #1

3
0 2
1 2
3 3

样例输出 #1

1

样例 #2

样例输入 #2

3
1 0
2 3
0 4

样例输出 #2

-1

样例 #3

样例输入 #3

我们提供了三组额外的样例,请参考stone文件夹。

样例输出 #3

我们提供了三组额外的样例,请参考stone文件夹。

提示

数据范围:

对于10%的数据,我们保证1<=n<=201<=n<=20

对于30%的数据,我们保证1<=n<=1031<=n<=10^3

对于100%的数据,我们保证1<=n<=105,0<=ai,bi<=1091<=n<=10^5,0<=a_i,b_i<=10^9