{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"Output 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."},{"iden":"examples","content":"Input7 42 1 3 3 4 2 3Output1Input7 42 1 3 3 4 3 2Output2"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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.","simple_statement":"You are given n bloggers and need at least m video reviews. Each blogger i will make a video if:  \n- they are convinced (interested), OR  \n- at least a[i] videos already exist.  \n\nYou can choose which bloggers to convince.  \nFind the minimum number of bloggers you need to convince to get at least m videos.","has_page_source":false}