AT_abc313_f [ABC313F] Flip Machines

有 $N$ 张编号为 $1$ 到 $N$ 的卡片。每张卡片的正反两面分别写有整数，对于第 $i$ 张卡片，正面写有 $A_i$，反面写有 $B_i$。一开始，所有卡片都正面朝上。 现在有 $M$ 台机器，编号为 $1$ 到 $M$。第 $j$ 台机器关联两个 $1$ 到 $N$ 之间的整数 $X_j, Y_j$（可以相同）。每次启动第 $j$ 台机器时，有 $\frac{1}{2}$ 的概率将编号为 $X_j$ 的卡片翻面，剩下的 $\frac{1}{2}$ 的概率将编号为 $Y_j$ 的卡片翻面。每次启动的概率彼此独立。 现在，すぬけ君将依次进行以下操作： 1. 选择一个由 $1$ 到 $M$ 之间的整数构成的集合 $S$。 2. 按照编号从小到大的顺序，依次启动 $S$ 中编号的机器各一次。 请你求出，すぬけ君如何选择 $S$，才能使“所有操作结束后，各卡片当前朝上的面上的整数之和”的期望值最大，并输出这个最大期望值。

输入按以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ > $\vdots$ > $A_N$ $B_N$ > $X_1$ $Y_1$ > $\vdots$ > $X_M$ $Y_M$

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

### 限制条件 - $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$ - 输入均为整数 ### 样例解释 1 如果选择 $S$ 为空集，则不会启动任何机器，此时“所有操作结束后各卡片当前朝上的面上的整数之和”的期望值为 $3+10+5=18$。如果选择 $S=\{1\}$，则启动机器 $1$， - 若卡片 $X_1=1$ 被翻面，则和为 $10+10+5=25$； - 若卡片 $Y_1=2$ 被翻面，则和为 $3+6+5=14$。 因此期望值为 $\frac{25+14}{2}=19.5$。 所以最大期望值为 $19.5$。 ### 样例解释 2 可能存在多台机器拥有相同的 $(X_j, Y_j)$。 由 ChatGPT 4.1 翻译