{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You work in a company which organizes marriages. Marriages are not that easy to fullfill, so, the job is quite difficult for you.\n\nThe job gets even more difficult when people have lots and lots of preferences. Some prioritize family background, some prioritize education, etc.\n\nYour company is still losing money and you want to help overcome this financial crisis by arranging as much marriages as possible So, you collected **N** bio-data of men and **N** bio-data of women. After analyzing quite a lot you calculated the priority index of each pair of men and women.\n\nFinally, you want to arrange **N** marriage ceremonies such that the total priority index is maximized. Remember that each man should be paired with a woman and only monogamous families should be formed.\n"}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026#8804; 100)** denoting the number of test cases.\n\nEach case contains an integer **N (1 \u0026#8804; n \u0026#8804; 16)** denoting the number of men or women. Each of the next **N** lines will contain **N** integers each. The **j\u003csup\u003eth\u003c/sup\u003e** integer in the **i\u003csup\u003eth\u003c/sup\u003e** line denotes the priority index between the **i\u003csup\u003eth\u003c/sup\u003e** man and **j\u003csup\u003eth\u003c/sup\u003e** woman. All the integers will be positive and not greater than **10000**.\n"}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the maximum possible priority index after all the marriages have been arranged."}},{"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\n2\n1 5\n2 1\n3\n1 2 3\n6 5 4\n8 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 7\nCase 2: 16\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}