{"problem":{"name":"C. Heidi and Library (hard)","description":{"content":"The good times at Heidi's library are over. Marmots finally got their internet connections and stopped coming to the library altogether. Not only that, but the bookstore has begun charging extortionat","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF802C"},"statements":[{"statement_type":"Markdown","content":"The good times at Heidi's library are over. Marmots finally got their internet connections and stopped coming to the library altogether. Not only that, but the bookstore has begun charging extortionate prices for some books. Namely, whereas in the previous versions each book could be bought for 1 CHF, now the price of book _i_ is _c__i_ CHF.\n\n## Input\n\nThe first line of input will contain two integers _n_ and _k_ (). The second line will contain _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_) – the sequence of book requests. The third line contains _n_ integers _c_1, _c_2, ..., _c__n_ (0 ≤ _c__i_ ≤ 106) – the costs of the books.\n\n## Output\n\nOn a single line print the minimum cost of buying books at the store so as to satisfy all requests.\n\n[samples]\n\n## Note\n\nThe first three sample cases are repeated, but the fourth one is new.\n\nIn the fourth test case, when buying book 3, Heidi should discard either book 1 or 2. Even though book 2 will be requested later than book 1, she should keep it, because it is so expensive to buy again.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Heidi 图书馆的好时光已经结束。土拨鼠终于接上了互联网，再也不来图书馆了。不仅如此，书店也开始对某些书籍收取天价费用。具体来说，以前每本书只需 1 CHF，但现在第 #cf_span[i] 本书的价格为 #cf_span[ci] CHF。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k] ()。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 书籍请求序列。第三行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[0 ≤ ci ≤ 10^6]) —— 书籍的价格。\n\n请在一行中输出为满足所有请求而购买书籍所需的最小花费。\n\n前三个示例与之前相同，但第四个是新增的。\n\n在第四个测试用例中，当购买书 #cf_span[3] 时，Heidi 应当丢弃书 #cf_span[1] 或 #cf_span[2] 中的一本。尽管书 #cf_span[2] 会在书 #cf_span[1] 之后被请求，她仍应保留它，因为再次购买它代价太高。\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k] ()。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ n]) —— 书籍请求序列。第三行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn] (#cf_span[0 ≤ ci ≤ 10^6]) —— 书籍的价格。\n\n## Output\n\n请在一行中输出为满足所有请求而购买书籍所需的最小花费。\n\n[samples]\n\n## Note\n\n前三个示例与之前相同，但第四个是新增的。在第四个测试用例中，当购买书 #cf_span[3] 时，Heidi 应当丢弃书 #cf_span[1] 或 #cf_span[2] 中的一本。尽管书 #cf_span[2] 会在书 #cf_span[1] 之后被请求，她仍应保留它，因为再次购买它代价太高。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n, k \\in \\mathbb{N} $, with $ 1 \\leq k \\leq n $.\n\nLet $ \\mathbf{a} = (a_1, a_2, \\dots, a_n) \\in \\{1, 2, \\dots, n\\}^n $ be the sequence of book requests.\n\nLet $ \\mathbf{c} = (c_1, c_2, \\dots, c_n) \\in \\mathbb{R}_{\\geq 0}^n $ be the cost vector, where $ c_i $ is the cost of book $ i $.\n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of books initially purchased (at most $ k $ books).\n\nAt each request $ a_t $ (for $ t = 1, 2, \\dots, n $), if $ a_t \\notin S $, then $ a_t $ must be purchased (adding it to $ S $), and the cost $ c_{a_t} $ is incurred. If $ |S| > k $ after a purchase, one book $ b \\in S \\setminus \\{a_t\\} $ must be discarded (removed from $ S $) to restore $ |S| = k $.\n\nThe goal is to choose the initial set $ S_0 $ (with $ |S_0| \\leq k $) and, for each request, decide which book to discard (if necessary), so as to **minimize the total cost** of all purchases.\n\nDefine the **minimum total cost** as:\n\n$$\n\\min_{\\substack{S_0 \\subseteq \\{1,\\dots,n\\} \\\\ |S_0| \\leq k}} \\sum_{t=1}^{n} \\left[ a_t \\notin S_{t-1} \\right] \\cdot c_{a_t}\n$$\n\nwhere $ S_t $ is the set of books in cache after processing request $ t $, and $ S_t $ is obtained from $ S_{t-1} $ by:\n\n- Adding $ a_t $ if $ a_t \\notin S_{t-1} $,\n- Then, if $ |S_t| > k $, removing exactly one book $ b \\in S_t \\setminus \\{a_t\\} $ (chosen optimally).\n\nThe problem reduces to computing the minimal total purchase cost under the above cache eviction policy, with capacity $ k $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF802C","tags":["flows","graphs"],"sample_group":[["4 80\n1 2 2 1\n1 1 1 1","2"],["4 1\n1 2 2 1\n1 1 1 1","3"],["4 2\n1 2 3 1\n1 1 1 1","3"],["7 2\n1 2 3 1 1 1 2\n1 10 1 0 0 0 0","13"]],"created_at":"2026-03-03 11:00:39"}}