F - Flip Machines Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 625 点

問題文

1 から N までの番号が付けられた N 枚のカードがあります。 カードのそれぞれの面には整数が書かれており、カード i の表には A_i が、裏には B_i が書かれています。 最初、全てのカードは表を向いています。

今ここに M 台のマシーンがあり、1 から M までの番号が付けられています。 マシーン j は（相異なるとは限らない）2 つの 1 以上 N 以下の整数 X_j,Y_j を持っており、マシーン j が起動されると、 \frac{1}{2} の確率でカード X_j を、残りの \frac{1}{2} の確率でカード Y_j を裏返します。 この確率は各起動ごとに独立です。

すぬけくんは今から以下の操作を順に行います。

  1. 1 以上 M 以下の整数からなる集合 S を選ぶ。
  2. S に含まれる番号のマシーンを、番号が小さい順に 1 度ずつ起動する。

すぬけくんがうまく 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

Score : 625 points

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