{"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 \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/c3c77c406a120e9e6c632a7a3d0cfeac?v\u003d1715954545\" alt\u003d\"/problems/catering/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003ePaul owns a catering company and business is booming. The\n company has \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e catering\n teams, each in charge of one set of catering equipment. Every\n week, the company accepts \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e catering requests for various\n events. For every request, they send a catering team with their\n equipment to the event location. The team delivers the food,\n sets up the equipment, and instructs the host on how to use the\n equipment and serve the food. After the event, the host is\n responsible for returning the equipment back to Paul’s company.\n\n \u003cp\u003eUnfortunately, in some weeks the number of catering teams is\n less than the number of requests, so some teams may have to be\n used for more than one event. In these cases, the company\n cannot wait for the host to return the equipment and must keep\n the team on-site to move the equipment to another location. The\n company has an accurate estimate of the cost to move a set of\n equipment from any location to any other location. Given these\n costs, Paul wants to prepare an Advance Catering Map to service\n the requests while minimizing the total moving cost of\n equipment (including the cost of the first move), even if that\n means not using all the available teams. Paul needs your help\n to write a program to accomplish this task. The requests are\n sorted in ascending order of their event times and they are\n chosen in such a way that for any \u003cspan class\u003d\"tex2jax_process\"\u003e$i \u0026lt; j$\u003c/span\u003e, there is enough time to\n transport the equipment used in the \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{th}$\u003c/span\u003e request to the location of\n the \u003cspan class\u003d\"tex2jax_process\"\u003e$j^{th}$\u003c/span\u003e request.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe first line of input contains two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 100$\u003c/span\u003e) and \u003cspan class\u003d\"tex2jax_process\"\u003e$k$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le k \\le 100$\u003c/span\u003e) which are the number of requests and the\n number of catering teams, respectively. Following that are\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, where the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{th}$\u003c/span\u003e line contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n-i+1$\u003c/span\u003e integers between\n \u003cspan class\u003d\"tex2jax_process\"\u003e$0$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\, 000\\, 000$\u003c/span\u003e inclusive. The\n \u003cspan class\u003d\"tex2jax_process\"\u003e$j^{th}$\u003c/span\u003e number in the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i^{th}$\u003c/span\u003e line is the cost\n of moving a set of equipment from location \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e to location \u003cspan class\u003d\"tex2jax_process\"\u003e$i+j$\u003c/span\u003e. The company is at location\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e and the \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e requests are at locations\n \u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n+1$\u003c/span\u003e.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the minimum moving cost to service all requests.\n (This amount does not include the cost of moving the equipment\n back to the catering company.)\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\u003e3 2\n40 30 40\n50 10\n50\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e80\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\u003e3 2\n10 10 10\n20 21\n21\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}