103135: [Atcoder]ABC313 F - Flip Machines

Problem Statement

There are $N$ cards numbered $1$ through $N$. Each face of a card has an integer written on it; card $i$ has $A_i$ on its front and $B_i$ on its back. Initially, all cards are face up.

There are $M$ machines numbered $1$ through $M$. Machine $j$ has two (not necessarily distinct) integers $X_i$ and $Y_i$ between $1$ and $N$. If you power up machine $j$, it flips card $X_i$ with the probability of $\frac{1}{2}$, and flips card $Y_i$ with the remaining probability of $\frac{1}{2}$. This probability is independent for each power-up.

Snuke will perform the following procedure.

1. Choose a set $S$ consisting of integers from $1$ through $N$.
2. For each element in $S$ in ascending order, power up the machine with that number.

Among Snuke's possible choices of $S$, find the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure.

Constraints

• $1\leq N \leq 40$
• $1\leq M \leq 10^5$
• $1\leq A_i,B_i \leq 10^4$
• $1\leq X_j,Y_j \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

Output

Print the answer. Your output is considered correct if the absolute or relative difference from the true value is at most $10^{-6}$.

Sample Input 1

3 1
3 10
10 6
5 2
1 2

Sample Output 1

19.500000

If $S$ is chosen to be an empty set, no machine is powered up, so the expected sum of the integers written on the face-up sides of the cards after the procedure is $3+10+5=18$.

If $S$ is chosen to be $\lbrace 1 \rbrace$, machine $1$ is powered up.

• If card $X_1 = 1$ is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is $10+10+5=25$.
• If card $Y_1 = 2$ is flipped, the expected sum of the integers written on the face-up sides of the cards after the procedure is $10+10+5=25$.

Thus, the expected value is $\frac{25+14}{2} = 19.5$.

Therefore, the maximum expected value of the sum of the integers written on the face-up sides of the cards after the procedure is $19.5$.

Sample Input 2

1 3
5 100
1 1
1 1
1 1

Sample Output 2

100.000000

Different machines may have the same $(X_j,Y_j)$.

Sample Input 3

8 10
6918 9211
16 1868
3857 8537
3340 8506
6263 7940
1449 4593
5902 1932
310 6991
4 4
8 6
3 5
1 1
4 2
5 6
7 5
3 3
1 5
3 1

Sample Output 3

45945.000000

问题描述

有N张卡片，编号为1到N。每张卡片的一面写有一个整数；第i张卡片正面为A_i，背面为B_i。起初，所有卡片都是正面朝上。

有M台编号为1到M的机器。第j台机器有两个（不一定是不同的）整数X_j和Y_j，范围在1到N之间。如果你启动第j台机器，它将以$\frac{1}{2}$的概率翻转卡片X_j，然后以剩余的$\frac{1}{2}$概率翻转卡片Y_j。每次启动的概率是独立的。

Snuke将执行以下过程。

1. 选择一个由1到M之间的整数构成的集合S。
2. 按照升序顺序，对S中的每个元素，启动对应编号的机器。

在Snuke可能选择的S中，找出过程结束后卡片正面朝上的整数之和的期望值的最大值。

限制条件

• $1\leq N \leq 40$
• $1\leq M \leq 10^5$
• $1\leq A_i,B_i \leq 10^4$
• $1\leq X_j,Y_j \leq N$
• 所有的输入值都是整数。

输入

输入数据通过标准输入给出，格式如下：

$N$ $M$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

输出

打印答案。如果输出与真实值的绝对差或相对差不超过$10^{-6}$，则认为你的输出是正确的。

样例输入1

3 1
3 10
10 6
5 2
1 2

样例输出1

19.500000

如果选择S为空集，那么没有机器启动，因此过程结束后卡片正面朝上的整数之和的期望值为$3+10+5=18$。

如果选择S为$\lbrace 1 \rbrace$，则启动第1台机器。

• 如果卡片X_1 = 1被翻转，过程结束后卡片正面朝上的整数之和的期望值为$10+10+5=25$。
• 如果卡片Y_1 = 2被翻转，过程结束后卡片正面朝上的整数之和的期望值为$3+6+5=14$。

因此，期望值为$\frac{25+14}{2} = 19.5$。

因此，过程结束后卡片正面朝上的整数之和的期望值的最大值为19.5。

样例输入2

1 3
5 100
1 1
1 1
1 1

样例输出2

100.000000

不同的机器可以有相同的$(X_j,Y_j)$。

样例输入3

8 10
6918 9211
16 1868
3857 8537
3340 8506
6263 7940
1449 4593
5902 1932
310 6991
4 4
8 6
3 5
1 1
4 2
5 6
7 5
3 3
1 5
3 1

样例输出3

45945.000000