{"raw_statement":[{"iden":"statement","content":"With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $n$ people moving into $m$ houses which are arranged in a row. The houses are numbered from $1$ to $m$ (both inclusive). House $u$ and $v$ are neighboring houses, if and only if $|u-v|=1$. We need to assign each person to a house so that no two people will move into the same house. If two people move into a pair of neighboring houses, they will become neighbors of each other.\n\nSome people like to have neighbors while some don't. For the $i$-th person, if he has at least one neighbor, his happiness will be $a_i$; Otherwise if he does not have any neighbor, his happiness will be $b_i$.\n\nAs the planner of this community, you need to maximize the total happiness."},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $m$ ($1 \\le n \\le 5 \\times 10^5$, $1 \\le m \\le 10^9$, $n \\le m$) indicating the number of people and the number of houses.\n\nFor the following $n$ lines, the $i$-th line contains two integers $a_i$ and $b_i$ ($1 \\le a_i, b_i \\le 10^9$) indicating the happiness of the $i$-th person with and without neighbors.\n\nIt's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$."},{"iden":"output","content":"For each test case output one line containing one integer indicating the maximum total happiness."},{"iden":"note","content":"For the first sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ to $4$ move into house $3$ to $5$. Thus, person $1$ have no neighbors while person $2$ to $4$ have neighbors. The answer is $100 + 100 + 100 + 100 = 400$. Of course, we can also let person $2$ to $4$ move into house $1$ to $3$ and let person $1$ move into house $5$. This will also give us $400$ total happiness.\n\nFor the second sample test case, as there are only $2$ houses, person $1$ and $2$ have to be neighbors. The answer is $1 + 1 = 2$.\n\nFor the third sample test case, the optimal strategy is to let person $1$ move into house $1$ and let person $2$ move into house $3$. Thus, both of them have no neighbors. The answer is $50 + 1000 = 1050$."}],"translated_statement":null,"sample_group":[["3\n4 5\n1 100\n100 1\n100 1\n100 1\n2 2\n1 10\n1 10\n2 3\n100 50\n1 1000","400\n2\n1050"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}