{"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\u003eYour university wants to build a new walkway, and they want\n at least part of it to be covered. There are certain points\n which must be covered. It doesn’t matter if other points along\n the walkway are covered or not.\u003c/p\u003e\n\n \u003cp\u003eThe building contractor has an interesting pricing scheme.\n To cover the walkway from a point at \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e to a point at \u003cspan class\u003d\"tex2jax_process\"\u003e$y$\u003c/span\u003e, they will charge \u003cspan class\u003d\"tex2jax_process\"\u003e$c + (x-y)^2$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e is a constant. Note that it is\n possible for \u003cspan class\u003d\"tex2jax_process\"\u003e$x\u003dy$\u003c/span\u003e. If so,\n then the contractor would simply charge \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e.\u003c/p\u003e\n\n \u003cp\u003eGiven the points along the walkway and the constant\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e, what is the minimum\n cost to cover the walkway?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eInput consists of a single test case. The test case will\n begin with a line with two integers, \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 1\\, 000\\, 000$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le c \\le 10^{9}$\u003c/span\u003e), where \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e is the number of points which must\n be covered, and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e is the\n contractor’s constant. Each of the following \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines will contain a single\n integer, representing a point along the walkway that must be\n covered. The points will be in order, from smallest to largest.\n All of the points will be in the range from \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$10^9$\u003c/span\u003e, inclusive.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eOutput a single integer, representing the minimum cost to\n cover all of the specified points. All possible inputs yield\n answers which will fit in a signed \u003cspan class\u003d\"tex2jax_process\"\u003e$64$\u003c/span\u003e-bit integer.\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\u003e10 5000\n1\n23\n45\n67\n101\n124\n560\n789\n990\n1019\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e30726\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}