Alice and Bonnie are sisters, but they don't like each other very much. So when some old family photos were found in the attic, they started to argue about who should receive which photos. In the end, they decided that they would take turns picking photos. Alice goes first.

There are n stacks of photos. Each stack contains exactly two photos. In each turn, a player may take only a photo from the top of one of the stacks.

Each photo is described by two non-negative integers a and b, indicating that it is worth a units of happiness to Alice and b units of happiness to Bonnie. Values of a and b might differ for different photos.

It's allowed to pass instead of taking a photo. The game ends when all photos are taken or both players pass consecutively.

The players don't act to maximize their own happiness. Instead, each player acts to maximize the amount by which her happiness exceeds her sister's. Assuming both players play optimal, find the difference between Alice's and Bonnie's happiness. That is, if there's a perfectly-played game such that Alice has x happiness and Bonnie has y happiness at the end, you should PRint x?-?y.

The first line of input contains a single integer n (1?≤?n?≤?100?000) — the number of two-photo stacks. Then follow n lines, each describing one of the stacks. A stack is described by four space-separated non-negative integers a1, b1, a2 and b2, each not exceeding 109. a1 and b1 describe the top photo in the stack, while a2 and b2 describe the bottom photo in the stack.

Output a single integer: the difference between Alice's and Bonnie's happiness if both play optimally.

212 3 4 71 15 9 1output
1input
25 4 8 84 12 14 0output
4input
10 10 0 10output
-10
題意：
給出n對照片，Alice和Bonnie輪流取照片，每張照片有兩個值a 和 b ，
a表示Alice取走這張照片獲得的喜悅值，b表示Bonnie取走這張照片獲得的喜悅值，
（每對照片只有當第一張照片被取走后才能取第二張），當輪到一個人時，他可以選擇不取，當連續兩輪兩個人都不取時，游戲結束，
Alice 和 Bonnie都希望自己的喜悅值和對方的喜悅值差值最大，假設兩人都采取最佳策略，求Alice 和 Bonnie最后的喜悅值的差值
數據：
1 <= n <= 100000
接下來n行每行四個非負整數 a1,b1,a2,b2
a1,b1代表第一張照片，a2,b2代表第二張照片
a1,b1,a2,b2 不超過1e9
題解：
貪心。對于單張照片來看，因為目標是凈勝分，所以價值可認為是a+b，但是由于有先后的約束，需要分類討論。對每對照片分類，共3類:1 a1<=b2&&b1<=a2, 對于該對照片，雙方第一次選擇均為負收益，故直接忽略。2 非1, 且a1+b1<=a2+b2, 即對于該對照片，雙方的后手收益都好于先手收益，但是由于非1，必有a1>b2或b1>a2，即必有一方有正收益，所以這一方為了保證自己的正收益而不是零收益(忽略該物品)不得不選擇先手。3 其余情況。因為1和2排除了廢物品和后手有利物品，其余物品可以正常選擇，而顯然因為目標是最大化凈勝分，所以物品的價值可以定為a1+b1(第二輪則是a2+b2),正常的優先隊列貪心即可。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<vector>#include<queue>#include<stack>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define fi first#define se secondtypedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const int inf=0x3fffffff;const ll mod=1000000007;const int maxn=1e5+100;struct node{    ll a1,b1,a2,b2;    int tag;    node(ll a=0,ll b=0,ll c=0,ll d=0):a1(a),b1(b),a2(c),b2(d) {}    bool Operator <(const node &b)const{        return a1+b1<b.a1+b.b1;    }};priority_queue<node> q;int main(){    int n;    scanf("%d",&n);    ll ans=0;    rep(i,1,n+1)    {        ll a1,b1,a2,b2;        scanf("%lld%lld%lld%lld",&a1,&b1,&a2,&b2);        if(a1<b2&&b1<a2) continue;        else if(a1+b1<=a2+b2)        {            if(a1>=b2) ans+=a1-b2;            else ans+=a2-b1;        }        else        {            node t=node(a1,b1,a2,b2);            t.tag=1;            q.push(t);        }    }    int cnt=0;    while(!q.empty())    {        node t=q.top();        q.pop();        cnt++;        if(cnt&1)            ans+=t.a1;        else ans-=t.b1;        if(t.tag==1)        {            node t1=node(t.a2,t.b2,0,0);            t1.tag=0;            q.push(t1);        }    }    printf("%lld/n",ans);    return 0;}