{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"A party has been arranged for **n** richest people of the city \"Richtown\". They have set some strange rules such that only rich people can join the party. Also, when a person enters the party, he/she is given two cards - **entrance** and **exit** represented as **(x, y)**, where **x** is the integer written on the entrance card, and **y** is the integer written on the exit card. No two persons can have **entrance** (or exit) cards with the same integers written on them. When a person exits the party, he/she has to pay the dollar equivalent to the absolute difference of the integers in his entrance and exit cards.\n\nThough they were rich, they were intelligent and came up with a plan to exchange their cards in such a way that the total money paid by them is as low as possible. Any people can exchange cards multiple times and with multiple persons. But the entrance cards are distinguishable from the exit cards, so entrance cards are only exchangeable with entrance cards, and the same rule applies for exit cards.\n\nFor example, suppose there are three people having cards with (1, 5), (7, 3), (8, 10), then if they don\u0027t exchange cards, they have to pay |1-5| + |7 - 3| + |8 - 10| \u003d 10\\$. But if they exchange them to (1, 3), (7, 5), (8, 10) then they need to pay |1-3| + |7-5| + |8-10| \u003d 6\u003cspan\u003e$\u003c/span\u003e. But there is one problem, each person must pay at least **K**\u003cspan\u003e$\u003c/span\u003e otherwise, the organizers will suspect that they have been cheating. So, your job is to help them find a solution where they have to pay as little as possible without creating any suspicion."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 10)**, denoting the number of test cases.\n\nEach case starts with a blank line. Next line contains two integers **n (1 \u0026le; n \u0026le; 10000)** and **K (0 \u0026le; K \u0026le; 2)**. Each of the next **n** lines contains two integers (between **1** and **50000**) denoting the integers written on the entrance and exit cards respectively for **i\u003csup\u003eth\u003c/sup\u003e** person."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum amount of money they need to pay. If its impossible to do so, print `impossible`."}},{"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\n\n3 1\n1 1\n7 3\n8 10\n\n1 2\n10 9\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 10\nCase 2: impossible\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge, use faster I/O methods."}}]}