First, let us consider how to find the expected sum of integers written on the face-up sides of the cards after the operations completed. Among the machines in \(S\), we process those with \(X_j = Y_j\) first, as it always flips card \(X_j\). (The order of powering up machines does not affect which face each card end up in showing.) Now we assume that \(S\) only contains those with \(X_j \neq Y_j\). By the linearity of expected value, it is sufficient to find “the expected value of integers written on the face-up side of each card after the operations completed.” That is, we want to find the probability that the card ends up being face down. In fact, this probability is as simple as the following:

• \(\frac{1}{2}\) if there is a machine \(j \in S\) such that \(X_j = i\) or \(Y_j = i\);
• \(0\) otherwise.

Thus, “the expected value of integers written on the face-up side of each card after the operations completed” is:

• \(\frac{1}{2}\) if there is a machine \(j \in S\) such that \(X_j = i\) or \(Y_j = i\);
• \(A_i\) otherwise.

Now, consider the original problem. Regarding the machines with \(X_j = Y_j\), we can “flip card \(X_j\) if the integer on its front is less than that on its back” for all such machines \(j\) firsthand, by the expression of the expected value above. We now only consider the machines with \(X_j \neq Y_j\).

After processing machines with \(X_j = Y_j\), let \(P\) be the set of cards such that (integer on face-up side) \(\geq\) (integer on face-down side), and \(Q\) be (integer on face-up side) \(<\) (integer on face-down side). We add the sum of integers on the current side in advance, and let \(D_i := \frac{|A_i-B_i|}{2}\), to boil down the problem as follows:

• You are given a sequence of non-negative integers \(D=(D_1,D_2,\dots,D_N)\), integer sets \(P\) and \(Q\), and \(M\) pairs \((X_1,Y_1),(X_2,Y_2),\dots,(X_M,Y_M)\) of integers between \(1\) and \(N\), where \(P\cup Q = \{1,2,\dots,N\}\), \(P\cap Q=\emptyset\), and \(X_j \neq Y_j\) for all \(j\).
• Maximize the following value \(W\) by appropriately choosing a set \(S\) of integers between \(1\) and \(M\).
  • Let \(I\) be the set of indices \(i\) such that there exists \(j \in S\) with \(X_j = i\) or \(Y_j = i\).
  • \(\displaystyle W := \sum_{i \in (I \cap Q)}D_i - \sum_{i \in (I \cap P)}D_i\).

We introduce two algorithms to solve this problem. Both of them uses the following observations.

• We can assume that machines with \(X_j \in P\) and \(Y_j \in P\) is always unused.
• We can assume that machines with \(X_j \in P\) and \(Y_j \in P\) is always used.
• We consider the other machines. To assume \(X_j \in P\) and \(Y_j \in Q\), swap \(X_j\) and \(Y_j\) if necessary. Here, for a fixed \(I \cap P\), all the machines with \(X_j \in (I \cap P)\) must be used. Thus, this problem is boiled down to choosing appropriate \(I \cap P\).

Algorithm 1

Brute-force all \(I \cap P\). The optimal choice of machines for a fixed \(I \cap P\) is described above. The complexity is \(O(M+2^{|P|}N)\).

Algorithm 2

Perform the following bit DP (Dynamic Programming).

\[dp[i][S]=(\text{maximum }W\text{ when the first }i\text{ machines in }P\text{ are chosen, and the current }I \cap Q\text{ is }S).\]

The complexity is \(O(M+2^{|Q|}N)\).

Here, there is no absolute superiority between Algorithm 1 and Algorithm 2; when \(|P| < |Q|\), the former is superior, and when \(|P| > |Q|\), the latter is. If we use an appropriate algorithm depending on which of \(|P|\) and \(|Q|\) is larger, the complexity will be \(O(M+2^{\frac{N}{2}}N)\), as \(\min\{|P|,|Q|\} \leq \frac{N}{2}\). This is fast enough under the constraints of this problem.

Sample code (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;
}