翻转机器

题目描述

有 $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$ 到 $M$ 的整数组成的集合 $S$。
• 按编号从小到大的顺序,将 $S$ 中编号对应的机器各启动一次。

当 Snuke 适当选择 $S$ 时,求「所有操作结束后,各卡片正面朝上的一面所写整数的总和」的期望值的最大值。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。 当答案与真实值的绝对误差或相对误差不超过 $10^{-6}$ 时,判定为正确。

样例

3 1
3 10
10 6
5 2
1 2

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$。

1 3
5 100
1 1
1 1
1 1

100.000000

可能存在多台机器具有相同的 $(X_j, Y_j)$。

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

45945.000000

数据范围

• $1 \le N \le 40$
• $1 \le M \le 10^5$
• $1 \le A_i,B_i \le 10^4$
• $1 \le X_j,Y_j \le N$
• 输入均为整数