{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"There are **n** gifts and **n** boxes, each box can contain at most one gift. Now you want to pack all the gifts in the boxes such that your profit is as high possible.\n\nThe boxes are numbered from **1** to **n** and the gifts are numbered from **1** to **n**. You will be given an **(n x n)** matrix where **p\u003csub\u003eij\u003c/sub\u003e** denotes the profit if we put the **i\u003csup\u003eth\u003c/sup\u003e** gift into the **j\u003csup\u003eth\u003c/sup\u003e** box. Now your task is to pack all the gifts and maximize the profit."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 100)**, denoting the number of test cases.\n\nEach case starts with a line containing an integer **n (1 \u0026le; n \u0026le; 50)**. Each of the next **n** lines contains **n** space separated integers forming the matrix. The values in the matrix lie in the range **[0, 1000]**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the maximum profit."}},{"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\n4 3\n3 1\n3\n1 4 5\n5 7 6\n5 8 8\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 6\nCase 2: 18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}