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