{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eChính phủ của sao Hỏa không chỉ quan tâm đến việc tối ưu hóa các chuyến bay vũ trụ, mà còn muốn cải thiện hệ thống đường bộ của hành tinh.\u003c/p\u003e\u003cp\u003eMột trong những con đường cao tốc quan trọng nhất của sao Hỏa kết nối Thành phố Olymp và Kstolop, thủ đô của Cydonia. Trong vấn đề này, chúng ta chỉ xem xét con đường từ Kstolop đến Thành phố Olymp, nhưng không phải là con đường ngược lại (tức là con đường từ Thành phố Olymp đến Kstolop).\u003c/p\u003e\u003cp\u003eCon đường từ Kstolop đến Thành phố Olymp dài $$$\\ell$$$ kilomet. Mỗi điểm trên con đường có tọa độ $$$x$$$ ($$$0 \\le x \\le \\ell$$$), tương đương với khoảng cách từ Kstolop tính bằng kilomet. Vì vậy, Kstolop nằm ở điểm có tọa độ $$$0$$$, và Thành phố Olymp nằm ở điểm có tọa độ $$$\\ell$$$.\u003c/p\u003e\u003cp\u003eCó $$$n$$$ biển báo dọc theo con đường, biển báo thứ $$$i$$$ đặt một giới hạn tốc độ $$$a_i$$$. Giới hạn này có nghĩa là phải đi qua kilomet tiếp theo trong $$$a_i$$$ phút và có hiệu lực cho đến khi bạn gặp biển báo tiếp theo trên con đường. Có một biển báo ở đầu con đường (tức là ở điểm có tọa độ $$$0$$$), đặt giới hạn tốc độ ban đầu.\u003c/p\u003e\u003cp\u003eNếu bạn biết vị trí của tất cả các biển báo, việc tính toán thời gian cần thiết để lái xe từ Kstolop đến Thành phố Olymp không khó. Xem một ví dụ:\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/ea1f9c096794e139328bb0162cd91966?v\u003d1716728798\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"756px\"\u003e \u003c/center\u003e\u003cp\u003eỞ đây, bạn cần lái ba kilomet đầu tiên trong mỗi kilomet trong năm phút, sau đó một kilomet trong tám phút, sau đó bốn kilomet trong mỗi kilomet trong ba phút, và cuối cùng hai kilomet cuối cùng phải đi qua trong mỗi kilomet trong sáu phút. Tổng thời gian là $$$3\\cdot 5 + 1\\cdot 8 + 4\\cdot 3 + 2\\cdot 6 \u003d 47$$$ phút.\u003c/p\u003e\u003cp\u003eĐể tối ưu hóa giao thông đường bộ, Chính phủ của sao Hỏa quyết định loại bỏ không quá $$$k$$$ biển báo đường. Không thể loại bỏ biển báo ở đầu con đường, nếu không, sẽ không có giới hạn ở đầu. Bằng cách loại bỏ các biển báo này, Chính phủ cũng muốn giảm thiểu thời gian cần thiết để lái xe từ Kstolop đến Thành phố Olymp.\u003c/p\u003e\u003cp\u003eCác doanh nghiệp công nghiệp lớn nhất đặt tại Cydonia, vì vậy việc ưu tiên là tối ưu hóa giao thông đường bộ từ Thành phố Olymp. Vì vậy, Chính phủ của sao Hỏa muốn bạn loại bỏ các biển báo theo cách mô tả ở trên.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa ba số nguyên $$$n$$$, $$$\\ell$$$, $$$k$$$ ($$$1 \\le n \\le 500$$$, $$$1 \\le \\ell \\le 10^5$$$, $$$0 \\le k \\le n-1$$$), số lượng biển báo trên con đường, khoảng cách giữa các thành phố và số lượng tối đa biển báo bạn có thể loại bỏ.\u003c/p\u003e\u003cp\u003eDòng thứ hai chứa $$$n$$$ số nguyên $$$d_i$$$ ($$$d_1 \u003d 0$$$, $$$d_i \u0026lt; d_{i+1}$$$, $$$0 \\le d_i \\le \\ell - 1$$$) — tọa độ của tất cả các biển báo.\u003c/p\u003e\u003cp\u003eDòng thứ ba chứa $$$n$$$ số nguyên $$$a_i$$$ ($$$1 \\le a_i \\le 10^4$$$) — giới hạn tốc độ.\u003c/p\u003e"}},{"title":"Kết quả","value":{"format":"HTML","content":"\u003cp\u003eIn một số nguyên duy nhất — thời gian tối thiểu có thể lái xe từ Kstolop đến Thành phố Olymp trong phút, nếu bạn loại bỏ không quá $$$k$$$ biển báo đường.\u003c/p\u003e"}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e4 10 0\n0 3 4 8\n5 8 3 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e47\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e4 10 2\n0 3 4 8\n5 8 3 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e38\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, bạn không thể loại bỏ các biển báo. Vì vậy, câu trả lời là $$$47$$$, như đã nói trong các câu trên.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, bạn có thể loại bỏ biển báo thứ hai và thứ tư. Trong trường hợp này, bạn cần lái xe qua bốn kilomet trong $$$4\\cdot5 \u003d 20$$$ phút, sau đó lái xe qua sáu kilomet trong $$$6\\cdot3 \u003d 18$$$ phút, vì vậy tổng thời gian là $$$4\\cdot5 + 6\\cdot3 \u003d 38$$$ phút.\u003c/p\u003e"}}]}