AT_abc313_f [ABC313F] Flip Machines

[problemUrl]: https://atcoder.jp/contests/abc313/tasks/abc313_f $ 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 $ を選んだとき、「すべての操作が終了した後に各カードが向いている面に書かれた整数の合計」の期待値が最大でいくつになるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ - 入力は全て整数 ### Sample Explanation 1 $ 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 $ です。 ### Sample Explanation 2 同じ $ (X_j,Y_j) $ を持つマシーンが複数存在することもあります。