まず、\(S\) を固定した上で、「すべての操作が終了した後に各カードが向いている面に書かれた整数の合計」の期待値の求め方について考えます。\(S\) に含まれるマシーンのうち、\(X_j = Y_j\) であるようなものは必ずカード \(X_j\) を裏返すので先に処理します（マシーンを起動させる順番は最終的なカードの裏表に影響しません）。以下、\(S\) には \(X_j \neq Y_j\) であるようなマシーンのみが入っているものとします。期待値の線形性より、各カード \(i\) について「すべての操作が終了した後にそのカードが向いている面に書かれた整数」の期待値が求まればよいです。これはすなわち、各カード \(i\) について「すべての操作が終了した後にそのカードが裏を向いている確率」を求めることと同義です。この確率は、実は以下のような簡単な形で表せます。

• \(X_j = i\) または \(Y_j = i\) であるようなマシーン \(j \in S\) が存在するならば、\(\frac{1}{2}\)
• そうでないならば、\(0\)

これを期待値の形に戻して考えると、「すべての操作が終了した後にカード \(i\) が向いている面に書かれた整数」の期待値は、

• \(X_j = i\) または \(Y_j = i\) であるようなマシーン \(j \in S\) が存在するならば、\(\frac{A_i + B_i}{2}\)
• そうでないならば、\(A_i\)

と表されます。

では元の問題について考えます。まずは \(X_j = Y_j\) であるようなマシーンについてですが、「カード \(X_j\) が向いている面に書かれた整数が反対の面に書かれた整数より小さいならば、カード \(X_j\) を裏返す」という操作を、\(X_j = Y_j\) であるようなすべての \(j\) について最初に行ってしまって損しないことが上述の期待値の表式から分かります。以下、\(X_j \neq Y_j\) であるようなマシーンのみについて考えます。

\(X_j = Y_j\) であるようなマシーンを処理し終えた時点で、「(向いている面に書かれた整数) \(\geq\) (反対の面に書かれた整数)」であるカードの集合を \(P\)、「(向いている面に書かれた整数) \(<\) (反対の面に書かれた整数)」であるカードの集合を \(Q\) とします。各カードが今向いている面に書かれた整数の合計を答えに予め加算し、\(D_i := \frac{|A_i-B_i|}{2}\) とおけば、本問題は以下の形に帰着されます。

• 非負整数列 \(D=(D_1,D_2,\dots,D_N)\)、整数の集合 \(P,Q\)、\(1\) 以上 \(N\) 以下の整数からなる \(M\) 個のペア \((X_1,Y_1),(X_2,Y_2),\dots,(X_M,Y_M)\) が与えられる。ただし、\(P\cup Q = \{1,2,\dots,N\},P\cap Q=\emptyset\) であり、すべての \(j\) について \(X_j \neq Y_j\) である。
• \(1\) 以上 \(M\) 以下の整数からなる集合 \(S\) をうまく選ぶことで、以下で定義される値 \(W\) を最大化せよ。
  • \(X_j = i\) または \(Y_j = i\) を満たす \(j \in S\) が存在するような \(i\) の集合を \(I\) とする。
  • \(\displaystyle W := \sum_{i \in (I \cap Q)}D_i - \sum_{i \in (I \cap P)}D_i\)

以下、この帰着後の問題を解くアルゴリズムを \(2\) 種類示します。どちらのアルゴリズムにおいても、次の考察を利用します。

• \(X_j \in P\) かつ \(Y_j \in P\) であるマシーンは必ず使わないとしてよい。
• \(X_j \in Q\) かつ \(Y_j \in Q\) であるマシーンは必ず使うとしてよい。
• それ以外のマシーンについて考える。必要ならば \(X_j\) と \(Y_j\) を入れ替えて、\(X_j \in P,Y_j \in Q\) とする。ここで、\(I \cap P\) が固定された場合を考えると、\(X_j \in (I \cap P)\) であるようなマシーンはすべて使うのが最適である（直感的な説明：\(X_j\) を裏返すことによる損失は既に確定してしまっているので、\(Y_j\) を裏返すことによる利益を取りに行くべきである）。よってこの問題は \(I \cap P\) をうまく選ぶ問題に帰着される。

アルゴリズム 1

\(I \cap P\) を全探索する。\(I \cap P\) を固定したときのマシーンの最適な選び方については上述の通りである。計算量は \(O(M+2^{|P|}N)\)。

アルゴリズム 2

以下のような bitDP を行う。

\[dp[i][S]=(P\text{ に含まれるカードのうち }i\text{ 個目まで見て、現在の }I \cap Q\text{ が }S\text{ であるときの }W\text{ の最大値})\]

計算量は \(O(M+2^{|Q|}N)\)。

さて、アルゴリズム 1 とアルゴリズム 2 の間に絶対的な優劣はなく、\(|P| < |Q|\) の場合は前者の方が、\(|P| > |Q|\) の場合は後者の方が優れています。ここで、\(|P|\) と \(|Q|\) の大小関係に応じて適した方のアルゴリズムを使うことにすると、\(\min\{|P|,|Q|\} \leq \frac{N}{2}\) より計算量は \(O(M+2^{\frac{N}{2}}N)\) になります。これは本問題の制約下で十分高速です。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    vector<int> x(m), y(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i] >> y[i];
        --x[i], --y[i];
        if (x[i] == y[i] and a[x[i]] < b[x[i]]) swap(a[x[i]], b[x[i]]);
    }
    int ans = 0;
    vector<int> p, q; // p: 選ぶと損　q: 選ぶと得
    vector<int> id(n);
    for (int i = 0; i < n; i++) {
        ans += a[i] * 2;
        int d = abs(a[i] - b[i]);
        if (a[i] >= b[i]) {
            id[i] = p.size();
            p.push_back(d);
        } else {
            id[i] = q.size();
            q.push_back(d);
        }
    }
    int ps = p.size(), qs = q.size();
    vector<ll> ls(ps);
    for (int i = 0; i < m; i++) {
        bool xp = (a[x[i]] >= b[x[i]]);
        bool yp = (a[y[i]] >= b[y[i]]);
        if (xp == yp) {
            if (!xp) {
                ans += q[id[x[i]]] + q[id[y[i]]];
                q[id[x[i]]] = q[id[y[i]]] = 0;
            }
        } else {
            if (!xp) swap(x[i], y[i]);
            ls[id[x[i]]] |= 1LL << id[y[i]];
        }
    }
    if (ps <= qs) {
        int mx = 0;
        for (int bit = 0; bit < (1 << ps); bit++) {
            int now = 0;
            ll cq = 0;
            for (int i = 0; i < ps; i++) {
                if (bit >> i & 1) {
                    now -= p[i];
                    cq |= ls[i];
                }
            }
            for (int i = 0; i < qs; i++) {
                if (cq >> i & 1) now += q[i];
            }
            mx = max(mx, now);
        }
        ans += mx;
    } else {
        vector dp(ps + 1, vector<int>(1 << qs, -1e9));
        dp[0][0] = 0;
        for (int i = 0; i < ps; i++) {
            for (int j = 0; j < (1 << qs); j++) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
                dp[i + 1][j | ls[i]] = max(dp[i + 1][j | ls[i]], dp[i][j] - p[i]);
            }
        }
        int mx = 0;
        for (int j = 0; j < (1 << qs); j++) {
            int now = dp[ps][j];
            for (int i = 0; i < qs; i++) {
                if (j >> i & 1) now += q[i];
            }
            mx = max(mx, now);
        }
        ans += mx;
    }
    cout << fixed << ans / 2. << endl;
}