#P770. 卡片游戏

卡片游戏

题目描述

小爱拿到了nn张卡片,每张卡片的正反面均写有一个数字,其中第ii张卡片的正面的数字为aia_i,反面的数字为bib_i

他想把每张卡片选取合适的一面后,放入下列算式中,卡片之间顺序可以交换,但每张卡片只能用一次。

A44F8CF9-7084-4923-B3A8-0DF4AE9AD8CC.png

请问,小爱通过以上操作,能得到的最大值是多少?

输入格式

第一行,一个正整数nn 接下来nn行,每行两个整数ai,bia_i,b_i

输出格式

输出共一行,一个整数,表示填入算式后,所能获得的最大值

6
10 -12
-17 -7
-7 5
-17 2
-4 3
-10 -8
62

样例解释 1

10 - (-17) + 5 -(-17) + 3 -(-10) = 62

数据范围

  • 对于 30%30\% 的数据,1n101\leq n \leq 10
  • 对于 60%60\% 的数据,1n1031\leq n \leq 10^3
  • 对于 100%100\% 的数据,1n1051\leq n \leq 10^5104ai104-10^4 \leq a_i \leq 10^4 且数据保证 nn 是偶数