Score : $625$ points

问题描述

设有 $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$ 的所有可能选择中，找出该过程结束后，卡片正面朝上的整数之和的最大期望值。

以上为通义千问 qwen-max 翻译，仅供参考。

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_j$ and $Y_j$ between $1$ and $N$. If you power up machine $j$, it flips card $X_j$ with the probability of $\frac{1}{2}$, and flips card $Y_j$ 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 $M$.
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 $3+6+5=14$.

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

update @ 2024/3/10 08:56:27