{"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\u003eYou are building advanced chips for machines. Making the\n chips is easy, but the power supply turns out to be an issue\n since the available batteries have varied power outputs.\u003c/p\u003e\n\n \u003cp\u003eConsider the problem of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e machines, each with two chips,\n where each chip is powered by \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e batteries. Surprisingly, it does\n not matter how much power each chip gets, but a machine works\n best when its two chips have power outputs as close as\n possible. The power output of a chip is simply the smallest\n power output of its \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e\n batteries.\u003c/p\u003e\n\n \u003cp\u003eYou have a stockpile of \u003cspan class\u003d\"tex2jax_process\"\u003e$2nk$\u003c/span\u003e batteries that you want to\n assign to the chips. It might not be possible to allocate the\n batteries so that in every machine both chips have equal power\n outputs, but you want to allocate them so that the differences\n are as small as possible. To be precise, you want to tell your\n customers that in all machines the difference of power outputs\n of the two chips is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e, and you want to make \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e as small as possible. To do this\n you must determine an optimal allocation of the batteries to\n the machines.\u003c/p\u003e\n\n \u003cp\u003eConsider Sample Input 1. There are \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e machines, each requiring\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3$\u003c/span\u003e batteries per chip,\n and a supply of batteries with power outputs \u003cspan class\u003d\"tex2jax_process\"\u003e$1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,\n 12$\u003c/span\u003e. You can, for instance, assign the batteries with\n power outputs \u003cspan class\u003d\"tex2jax_process\"\u003e$1, 3, 5$\u003c/span\u003e to\n one chip, those with power \u003cspan class\u003d\"tex2jax_process\"\u003e$2, 4,\n 12$\u003c/span\u003e to the other chip of the same machine, those with\n power \u003cspan class\u003d\"tex2jax_process\"\u003e$6, 8, 9$\u003c/span\u003e to the\n third chip, and those with power \u003cspan class\u003d\"tex2jax_process\"\u003e$7, 10, 11$\u003c/span\u003e to the fourth. The power\n outputs of the chips are \u003cspan class\u003d\"tex2jax_process\"\u003e$1, 2,\n 6$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e,\n respectively, and the difference between power outputs is\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e in both machines. Note\n that there are many other ways to achieve this result.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case\n consists of two lines. The first line contains two positive\n integers: the number of machines \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e and the number of batteries per\n chip \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2nk \\leq 10^6$\u003c/span\u003e). The second line\n contains \u003cspan class\u003d\"tex2jax_process\"\u003e$2nk$\u003c/span\u003e integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$p_ i$\u003c/span\u003e specifying the\n power outputs of the batteries (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq p_ i \\leq 10^9$\u003c/span\u003e).\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the smallest number \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e such that you can allocate the\n batteries so that the difference of power outputs of the two\n chips in each machine is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e.\u003c/p\u003e\n\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 3\n1 2 3 4 5 6 7 8 9 10 11 12\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\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 2\n3 1 3 3 3 3 3 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}