{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eA certain string-processing language allows the programmer to break a string into two pieces. Since this involves copying the old string, it costs n units of time to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks are made can affect the total amount of time used. For example, suppose we wish to break a 20 character string after characters 3, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If the breaks are made in left-to-right order, then the first break cost 20 units of time, the second break costs 17 units of time, and the third breaks costs 12 units of time, a total of 49 units of time (see the sample below). If the breaks are made in right-to-left order, then the first break costs 20 units of time, the second break costs 10 units of time, and the third break costs 8 units of time, a total of 38 units of time.\u003c/p\u003e\n\u003cp\u003eThe cost of making the breaks in left-to-right order:\n\u003c/p\u003e\u003cpre\u003ethisisastringofchars (original)\nthi sisastringofchars (cost:20 units)\nthi sisas tringofchars (cost:17 units)\nthi sisas tr ingofchars (cost:12 units)\n Total: 49 units.\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003eThe cost of making the breaks in right-to-left order:\n\u003c/p\u003e\u003cpre\u003ethisisastringofchars (original)\nthisisastr ingofchars (cost:20 units)\nthisisas tr ingofchars (cost:10 units)\nthi sisas tr ingofchars (cost: 8 units)\n Total: 38 units.\u003c/pre\u003e\u003cp\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eThere are several test cases! In each test case, the first line contains 2 integers N (2\u0026lt;\u003dN\u0026lt;\u003d10000000) and M (1\u0026lt;\u003dM\u0026lt;\u003d1000, M\u0026lt;N). N is the original length of the string, and M is the number of the breaks. The following lines contain M integers Mi (1\u0026lt;\u003dMi\u0026lt;N) in ascending order that represent the breaking positions from the string\u0027s left-hand end.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eOutput:\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003eFor each test case, output in one line the least cost to make all the breakings.\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eSample Input:\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e20 3\n3 8 10\u003c/pre\u003e\n\u003cp\u003e\u003cb\u003eSample Output:\u003c/b\u003e\u003c/p\u003e\n\u003cpre\u003e37\u003c/pre\u003e\n"}}]}