← 返回题目列表

Codeforces · 725/F

F. 家庭照片

中文机器翻译题面 查看原题

Alice和Bonnie是姐妹,但她们不太喜欢对方。因此,当阁楼上发现了一些家庭旧照片时,他们开始争论谁应该收到哪些照片。最后,他们决定轮流挑选照片。爱丽丝先走。

有 n 叠照片。每个堆栈包含恰好两张照片。在每一轮中,玩家只能从其中一叠的顶部拍摄一张照片。

每张照片都由两个非负整数 a 和 b 来描述,表示它值得 Alice 享受 1 个单位的幸福,值得 Bonnie 获得 b 个单位的幸福。对于不同的照片,a 和 b 的值可能不同。

允许通过而不拍照。当所有照片拍完或双方连续通过时,游戏结束。

玩家的行为并不是为了最大化自己的幸福。相反,每个玩家都会采取行动,以最大化她的幸福感超过她姐姐的幸福感。假设两个玩家都发挥最佳,找出爱丽丝和邦妮的幸福感之间的差异。也就是说,如果有一个完美的游戏,最后爱丽丝有 x 幸福,邦妮有 y 幸福,你应该打印 x - y。

输入

输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 两张照片堆栈的数量。然后接下来 n 行,每行描述其中一个堆栈。堆栈由四个空格分隔的非负整数 a1、b1、a2 和 b2 描述,每个整数不超过 109。a1 和 b1 描述堆栈中顶部的照片,而 a2 和 b2 描述堆栈中底部的照片。

输出

输出一个整数:如果爱丽丝和邦妮都发挥最佳,则他们的幸福感之间的差异。

示例

输入 #1

2
12 3 4 7
1 15 9 1

输出 #1

1

输入 #2

2
5 4 8 8
4 12 14 0

输出 #2

4

输入 #3

1
0 10 0 10

输出 #3

-10