{"problem":{"name":"Flip Machines","description":{"content":"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$ m","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc313_f"},"statements":[{"statement_type":"Markdown","content":"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.\nThere 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.\nSnuke will perform the following procedure.\n\n1.  Choose a set $S$ consisting of integers from $1$ through $M$.\n2.  For each element in $S$ in ascending order, power up the machine with that number.\n\nAmong 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.\n\n## Constraints\n\n*   $1\\leq N \\leq 40$\n*   $1\\leq M \\leq 10^5$\n*   $1\\leq A_i,B_i \\leq 10^4$\n*   $1\\leq X_j,Y_j \\leq N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$\n$\\vdots$\n$A_N$ $B_N$\n$X_1$ $Y_1$\n$\\vdots$\n$X_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc313_f","tags":[],"sample_group":[["3 1\n3 10\n10 6\n5 2\n1 2","19.500000\n\nIf $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$.\nIf $S$ is chosen to be $\\lbrace 1 \\rbrace$, machine $1$ is powered up.\n\n*   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$.\n*   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$.\n\nThus, the expected value is $\\frac{25+14}{2} = 19.5$.\nTherefore, 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$."],["1 3\n5 100\n1 1\n1 1\n1 1","100.000000\n\nDifferent machines may have the same $(X_j,Y_j)$."],["8 10\n6918 9211\n16 1868\n3857 8537\n3340 8506\n6263 7940\n1449 4593\n5902 1932\n310 6991\n4 4\n8 6\n3 5\n1 1\n4 2\n5 6\n7 5\n3 3\n1 5\n3 1","45945.000000"]],"created_at":"2026-03-03 11:01:14"}}