{"raw_statement":[{"iden":"problem statement","content":"In a two-dimensional plane, there are $N$ towns and $M$ chests. Town $i$ is at the coordinates $(X_i,Y_i)$, and chest $i$ is at the coordinates $(P_i,Q_i)$.\nTakahashi will go on a trip where he starts at the origin, visits all $N$ towns, and then returns to the origin.  \nIt is not mandatory to visit chests, but each chest contains an accelerator. Each time he picks up an accelerator, his moving speed gets multiplied by $2$.\nTakahashi's initial moving speed is $1$. Find the shortest time needed to complete the trip."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 12$\n*   $0 \\leq M \\leq 5$\n*   $-10^9 \\leq X_i,Y_i,P_i,Q_i \\leq 10^9$\n*   $(0,0)$, $(X_i,Y_i)$, and $(P_i,Q_i)$ are distinct.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $Y_1$\n$\\vdots$\n$X_N$ $Y_N$\n$P_1$ $Q_1$\n$\\vdots$\n$P_M$ $Q_M$"},{"iden":"sample input 1","content":"2 1\n1 1\n0 1\n1 0"},{"iden":"sample output 1","content":"2.5000000000\n\nHere is one optimal way to complete the trip.\n\n*   Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.\n*   Go the distance $1$ from chest $1$ to town $1$ at a speed of $2$, taking a time of $0.5$.\n*   Go the distance $1$ from town $1$ to town $2$ at a speed of $2$, taking a time of $0.5$.\n*   Go the distance $1$ from town $2$ to the origin at a speed of $2$, taking a time of $0.5$."},{"iden":"sample input 2","content":"2 1\n1 1\n0 1\n100 0"},{"iden":"sample output 2","content":"3.4142135624\n\nHere is one optimal way to complete the trip.\n\n*   Go the distance $1.41\\ldots$ from the origin to town $1$ at a speed of $1$, taking a time of $1.41\\ldots$.\n*   Go the distance $1$ from town $1$ to town $2$ at a speed of $1$, taking a time of $1$.\n*   Go the distance $1$ from town $2$ to the origin at a speed of $1$, taking a time of $1$."},{"iden":"sample input 3","content":"1 2\n4 4\n1 0\n0 1"},{"iden":"sample output 3","content":"4.3713203436\n\nHere is one optimal way to complete the trip.\n\n*   Go the distance $1$ from the origin to chest $1$ at a speed of $1$, taking a time of $1$.\n*   Go the distance $1.41\\ldots$ from chest $1$ to chest $2$ at a speed of $2$, taking a time of $0.707\\ldots$.\n*   Go the distance $5$ from chest $2$ to town $1$ at a speed of $4$, taking a time of $1.25$.\n*   Go the distance $5.65\\ldots$ from town $1$ to the origin at a speed of $4$, taking a time of $1.41\\ldots$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}