CF725F Family Photos

Alice 和 Bonnie 是姐妹，但她们并不是很喜欢彼此。因此当她们在阁楼发现了一些旧家族照片时，就开始争吵每个人应该拿哪些照片。最后，她们决定轮流挑选照片。Alice 先开始。 共有 $ n $ 堆照片。每一堆里正好有两张照片。在每一轮，玩家只能从某一堆的顶部拿走一张照片。 每一张照片用两个非负整数 $ a $ 和 $ b $ 表示，分别表示该照片对 Alice 和 Bonnie 的幸福值分别为 $ a $ 和 $ b $。对于不同照片，$ a $ 和 $ b $ 的值可能不同。 玩家可以选择跳过，而不是拿照片。当所有照片都被取走或连续两位玩家都跳过时，游戏结束。 玩家的目标并非仅仅最大化自己的总幸福值，而是最大化自己与对方之间幸福值的差距。假设两位玩家都采取最优策略，求最终 Alice 的幸福值减去 Bonnie 的幸福值的最大可能差值。也就是说，若最优情况下 Alice 的幸福值为 $ x $，Bonnie 的为 $ y $，请输出 $ x-y $。

输入第一行为一个整数 $ n $（$ 1\leq n\leq 100000 $），表示有多少堆照片。接下来的 $ n $ 行，每行描述一堆照片，包括四个以空格分隔的非负整数 $ a_{1} $、$ b_{1} $、$ a_{2} $、$ b_{2} $，均不超过 $ 10^{9} $。其中 $ a_{1} $、$ b_{1} $ 表示该堆顶部照片的信息，$ a_{2} $、$ b_{2} $ 表示底部照片的信息。

输出一个整数，表示在双方都采取最优策略的情况下，Alice 的幸福值与 Bonnie 的幸福值之差。

由 ChatGPT 5 翻译