{"problem":{"name":"K. Video Reviews","description":{"content":"The studio «Lodka Gaming» is engaged in advertising of their new game «.C.O.N.T.E.S.T: Unexpected Behaviour». The studio's marketer is planning to communicate with n videobloggers one by one (in the p","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10175K"},"statements":[{"statement_type":"Markdown","content":"The studio «Lodka Gaming» is engaged in advertising of their new game «.C.O.N.T.E.S.T: Unexpected Behaviour». The studio's marketer is planning to communicate with n videobloggers one by one (in the predetermined order, starting from the 1-st and ending with the n-th), offering them to record a video review on the game. All people are different and videobloggers are as well, therefore the i-th videoblogger will record a review in two cases: either he is interested in this game, or there are already at least ai video reviews on this game.\n\nThe studio wants to have at least m video reviews in the Internet. The game designer of «Lodka Gaming» understands these video reviews possibly would not appear by themselves, so he wants to _convince_ some video bloggers that they are actually interested in this game. Which minimal number of videobloggers are needed to be _convinced_?\n\nThe first line contains two integers n and m (1 ≤ n ≤ 200000, 1 ≤ m ≤ n) — the number of videobloggers and the required number of video reviews.\n\nThe second line contains n integers ai (0 ≤ ai ≤ 200000) — the minimal number of video reviews that should appear in the Internet so that the i-th videoblogger will record a review in case he is not interested in the game.\n\nOutput a single integer — the minimal number of videobloggers who have to be _convinced_ to record a video review on the game in order to achieve at least m total video reviews in the Internet.\n\n## Input\n\nThe first line contains two integers n and m (1 ≤ n ≤ 200000, 1 ≤ m ≤ n) — the number of videobloggers and the required number of video reviews.The second line contains n integers ai (0 ≤ ai ≤ 200000) — the minimal number of video reviews that should appear in the Internet so that the i-th videoblogger will record a review in case he is not interested in the game.\n\n## Output\n\nOutput a single integer — the minimal number of videobloggers who have to be _convinced_ to record a video review on the game in order to achieve at least m total video reviews in the Internet.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq m \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of non-negative integers, where $ a_i $ is the threshold for the $ i $-th videoblogger.  \n\nLet $ x_i \\in \\{0,1\\} $ indicate whether the $ i $-th videoblogger is **convinced** ($ x_i = 1 $) or not ($ x_i = 0 $).  \nLet $ r_i \\in \\{0,1\\} $ indicate whether the $ i $-th videoblogger **records** a review, defined as:  \n$$\nr_i = \n\\begin{cases}\n1 & \\text{if } x_i = 1 \\text{ or } \\sum_{j=1}^{i-1} r_j \\geq a_i \\\\\n0 & \\text{otherwise}\n\\end{cases}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200000 $  \n2. $ 1 \\leq m \\leq n $  \n3. $ 0 \\leq a_i \\leq 200000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. $ \\sum_{i=1}^n r_i \\geq m $  \n\n**Objective**  \nMinimize $ \\sum_{i=1}^n x_i $, subject to the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10175K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}