{"trustable":false,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003eYour search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e different books, numbered \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e through \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e \n\u003cp\u003eWe will look at the library\u0027s operation during \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e consecutive days. Heidi knows in advance that on the \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) precisely one person will come to the library, request to borrow the book \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, read it in a few hours, and return the book later on the same day.\u003c/p\u003e \n\u003cp\u003eHeidi desperately wants to please all her guests, so she will make sure to always have the book \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e available in the library on the \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day. During the night before the \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.\u003c/p\u003e \n\u003cp\u003eThere is a problem, though. The capacity of the library is \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e – this means that at any time, there can be at most \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e books at the library. If buying a new book would cause Heidi to have more than \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.\u003c/p\u003e \n\u003cp\u003eYou are given \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e and the sequence of requests for books \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of input will contain two integers \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ek\u003c/i\u003e\u003c/span\u003e (\u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/490b7cd1e802fcfbcbc28e7f37020697?v\u003d1598525239\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e). The second line will contain \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) – the sequence of book requests. The third line contains \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e \u003ci\u003ec\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ec\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, ..., \u003ci\u003ec\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ec\u003c/i\u003e \u003csub class\u003d\"lower-index\"\u003e \u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) – the costs of the books.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOn a single line print the minimum cost of buying books at the store so as to satisfy all requests.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 80\u003cbr\u003e1 2 2 1\u003cbr\u003e1 1 1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e2\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 1\u003cbr\u003e1 2 2 1\u003cbr\u003e1 1 1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e3\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e4 2\u003cbr\u003e1 2 3 1\u003cbr\u003e1 1 1 1\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e3\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"input\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e \n \u003cpre\u003e7 2\u003cbr\u003e1 2 3 1 1 1 2\u003cbr\u003e1 10 1 0 0 0 0\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e \n \u003cdiv class\u003d\"output\"\u003e \n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e \n \u003cpre\u003e13\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eThe first three sample cases are repeated, but the fourth one is new.\u003c/p\u003e \n\u003cp\u003eIn the fourth test case, when buying book \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e, Heidi should discard either book \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e or \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. Even though book \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e will be requested later than book \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e, she should keep it, because it is so expensive to buy again.\u003c/p\u003e"}}]}