{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eFarmer John built $n$ fences on his farm. The $i$-th fence is a line segment in the plane\u003cbr\u003ewhose two endpoints are $(x_{1i}, y_{1i})$ and $(x_{2i}, y_{2i})$. Two different fences\u003cbr\u003ecan only intersect at their endpoints.\u003cbr\u003eThe following picture shows an example layout of fences.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/3eda66926e824860b4931c04e8152ec2?v\u003d1726401424\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003eTo make cows happy, John will decorate the fences with rope lights.\u003cbr\u003eA fence can hang several rope lights paralleling to itself.\u003cbr\u003eHowever, a light can not be used alone.\u003cbr\u003eJohn can only make a decoration by using some lights together (we call it a \u003cb\u003estring of lights\u003c/b\u003e) and these lights will form a circle to decorate some fences (a light corresponds to a fence).\u003cbr\u003eIn the example, he can use three lights decorate three fences numbered $1, 2, 5$ which form a circle.\u003cbr\u003e\u003cbr\u003eA string of lights which decorate fences numbered $k_1,k_2,\\cdots,k_m$ costs John $\\sum_{i\u003d1}^m p_{k_i}$ dollars. The total cost is the sum of costs of each string. Notice that the cost for more than one \u003cb\u003estrings of lights\u003c/b\u003e should be accumulated.\u003cbr\u003eIn the example, suppose that he decorate the fences with two strings of lights. One string decorate three fences numbered $1, 2, 5$ and the other string decorate three fences numbered $1, 2, 3, 4$. Then the total cost should be $2\\times p_1+2\\times p_2+p_3+p_4+p_5 \u003d 106$ dollars.\u003cbr\u003e\u003cbr\u003eJohn can control the switch of \u003cb\u003eeach string\u003c/b\u003e of lights. He can switch on \u003cb\u003eall lights on that string\u003c/b\u003e or switch off\u003cbr\u003eall of them, but he cannot switch on some of they while keeping other lights on that string switched off.\u003cbr\u003eFor a fence, if even number of strings on it are switched on, then all the lights on that fence will not work; otherwise,\u003cbr\u003eall of them work. We define the shape of lights as a combination of status of each fence (considering the fences lit or not). A shape of lights might be achieved by arrangements of lights. The following picture shows all possible shape of\u003cbr\u003elights in the example. (Dash lines stands for fences where lights work and the solid stands for fences where lights\u003cbr\u003edon\u0027t work.)\u003cbr\u003e\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/33430647adeb19d698db52a5675804ce?v\u003d1726401424\"\u003e\u003c/center\u003e\u003cbr\u003e\u003cbr\u003eThe cows love lights, but they are fickle too. They want the lights arranged to form\u003cbr\u003edifferent shapes from day to day, so John need to make arrangement for decorations so that \u003cb\u003eevery possible shapes\u003c/b\u003e can be formed by switching on \u003cb\u003esome of\u003c/b\u003e the strings of lights and switching off the others.\u003cbr\u003eWhat is the minimum money John must spend to meet needs of cows.\u003cbr\u003e\u003cbr\u003eIn the example, he can decorate the fences with two strings of lights.\u003cbr\u003eOne string decorate three fences numbered $1, 2, 5$ and the other string decorate three fences numbered $1, 2, 3, 4$.\u003cbr\u003eIf he switch off all strings, then cows can get the first shape; if he switch on all strings, then cows can get the last shape; if he switch on only the first string, then then cows can get the third shape; if he switch on only the second string, then then cows can get the second shape. Thus, he can spend 106 dollars to meet need of cows, and it also\u003cbr\u003eturns out to be the minimum cost.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $t~(1\\le t\\le 8)$, meaning the total number of test cases.\u003cbr\u003eFor each test case, the first line of input contains $n~(1\\le n\\le 1000)$. The following $n$ lines describe the fences and each line will contain five space separated integers $x_{1i}$, $y_{1i}$, $x_{2i}$, $y_{2i}$ and $p_i$, where $|x_{1i}|,|y_{1i}|,|x_{2i}|,|y_{2i}|\\le 10^9$ and $1\\le p_i\\le 10^5$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one integer, which is the minimum money John should spend."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n5\r\n0 0 0 1 1\r\n0 0 1 0 1\r\n0 1 1 1 1\r\n1 0 1 1 1\r\n1 0 0 1 100\r\n9\r\n1 1 3 1 1\r\n1 1 1 3 2\r\n3 1 3 3 2\r\n1 3 3 3 1\r\n1 1 2 2 2\r\n2 2 3 3 3\r\n3 1 2 2 1\r\n2 2 1 3 2\r\n4 1 5 1 4\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 106\r\nCase #2: 22\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}