{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cp\u003eBesides the prestigious ACM-ICPC contest, Nha Trang\n University also hosted the Vietnamese Collegiate Olympiads in\n Informatics 2016. This Olympiad had several events where\n students compete individually to show their skills and\n knowledge.\u003c/p\u003e\n \u003cp\u003eAfter a successful contest this year, \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e junior students in Nha Trang\n University expressed their interests to join the team next year\n to represent their university. But in order for them to be at a\n medal contender level, the coach, Mr. Van, has to teach them\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e topics. The\n \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e student\n will require \u003cspan class\u003d\"tex2jax_process\"\u003e${a}_{i,j}$\u003c/span\u003e\n minutes to understand the \u003cspan class\u003d\"tex2jax_process\"\u003e${j}^\\textrm {th}$\u003c/span\u003e topic. Teaching\n \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e students \u003cspan class\u003d\"tex2jax_process\"\u003e${X}_{1}, {X}_{2},\\ldots , {X}_{k}$\u003c/span\u003e\n the \u003cspan class\u003d\"tex2jax_process\"\u003e${j}^\\textrm {th}$\u003c/span\u003e\n topic will require \u003cspan class\u003d\"tex2jax_process\"\u003e$max({a}_{{x}_{k,j}}, {a}_{{x}_{2,j}},\\ldots\n , {a}_{{x}_{k,j}})$\u003c/span\u003e minutes and teaching them all\n \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e topics will require\n \u003cspan class\u003d\"tex2jax_process\"\u003e$\\sum _{j\u003d1}^{M}\n max({a}_{{x}_{1,j}}, {a}_{{x}_{2,j}},\\ldots ,\n {a}_{{x}_{k,j}})$\u003c/span\u003e minutes.\u003c/p\u003e\n \u003cp\u003eGiven \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e - the number\n of students in a group to train, your task is to help Mr. Van\n decide who he should pick in order to minimize the total time\n he needs to teach them all \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e topics.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of several datasets. The first line of\n the input contains the number of datasets which is a positive\n integer and is not greater than \u003cspan class\u003d\"tex2jax_process\"\u003e$100$\u003c/span\u003e. The following lines describe\n the datasets.\u003c/p\u003e\n \u003cp\u003eEach dataset is described by the following lines:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe first line contains three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$N, M, Q$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq Q \\leq N \\leq 20, M \\leq 10\\,\n 000)$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm\n {th}$\u003c/span\u003e line of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e lines contains \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e${a}_{i,j}$\u003c/span\u003e \u003cspan class\u003d\"tex2jax_process\"\u003e$(0 \\leq {a}_{i,j} \\leq\n {10}^{9})$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe \u003cspan class\u003d\"tex2jax_process\"\u003e${u}^\\textrm\n {th}$\u003c/span\u003e line of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$Q$\u003c/span\u003e lines contains a query which\n is an integer \u003cspan class\u003d\"tex2jax_process\"\u003e$K$\u003c/span\u003e\n \u003cspan class\u003d\"tex2jax_process\"\u003e$(1 \\leq K \\leq N)$\u003c/span\u003e\n representing the number of students in the group that Mr.\n Van needs to train.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eFor each dataset, output \u003cspan class\u003d\"tex2jax_process\"\u003e$Q$\u003c/span\u003e lines where the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e line contains the\n minimal time required for the \u003cspan class\u003d\"tex2jax_process\"\u003e${i}^\\textrm {th}$\u003c/span\u003e query.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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 2 1\n1 3\n3 2\n1\n3 3 3\n1 4 9\n2 6 3\n3 5 5\n1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n11\n14\n18\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}