{"raw_statement":[{"iden":"statement","content":"Famous Berland coder and IT manager Linus Gates announced his next proprietary open-source system \"Winux 10.04 LTS\"\n\nIn this system command \"_dir -C_\" prints list of all files in the current catalog in multicolumn mode. \n\nLets define the multicolumn mode for number of lines l. Assume that filenames are already sorted lexicographically.\n\nExample of multi-column output:\n\nIn the example above width of output is equal to 19. \n\n\"_dir -C_\" command selects minimal l, such that width of the output does not exceed width of screen w.\n\nGiven information about filename lengths and width of screen, calculate number of lines l printed by \"_dir -C_\" command.\n\nFirst line of the input contains two integers n and w — number of files in the list and width of screen (1 ≤ n ≤ 105, 1 ≤ w ≤ 109).\n\nSecond line contains n integers fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ w).\n\nPrint one integer — number of lines l, printed by \"_dir -C_\" command.\n\n"},{"iden":"input","content":"First line of the input contains two integers n and w — number of files in the list and width of screen (1 ≤ n ≤ 105, 1 ≤ w ≤ 109).Second line contains n integers fi — lengths of filenames. i-th of those integers represents length of i-th filename in the lexicographically ordered list (1 ≤ fi ≤ w)."},{"iden":"output","content":"Print one integer — number of lines l, printed by \"_dir -C_\" command."},{"iden":"examples","content":"Input11 201 3 7 4 1 2 1 1 1 1 4Output3"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of files.  \nLet $ w \\in \\mathbb{Z}^+ $ be the screen width.  \nLet $ f = (f_1, f_2, \\dots, f_n) $ be a sequence of positive integers representing the lengths of filenames in lexicographic order, where $ 1 \\le f_i \\le w $.  \n\nLet $ l \\in \\mathbb{Z}^+ $ be the number of lines in multicolumn output.  \nLet $ c = \\lceil n / l \\rceil $ be the number of columns.  \n\nThe width of the output is defined as:  \n$$\n\\text{width}(l) = (c - 1) \\cdot \\min_{i \\in \\{1, \\dots, c\\}} \\left( \\max_{j \\in \\{1, \\dots, l\\}} f_{(j-1)c + i} \\right) + \\max_{j \\in \\{1, \\dots, l\\}} f_{(j-1)c + c}\n$$  \nBut more precisely, in standard multicolumn layout:  \nThe maximum width is the sum of the maximum filename length in each column, plus $ c - 1 $ spaces between columns.  \n\nActually, standard model:  \n- The output has $ l $ rows and $ c = \\lceil n / l \\rceil $ columns.  \n- The $ j $-th column contains filenames from index $ (j-1)l + 1 $ to $ \\min(jl, n) $.  \n- The width of column $ j $ is $ \\max \\{ f_i \\mid i \\in \\text{column } j \\} $.  \n- Total width = sum of column widths + $ (c - 1) $ spaces between them.  \n\nSo:  \nLet $ c = \\lceil n / l \\rceil $.  \nFor $ j = 1 $ to $ c $:  \nLet $ \\text{col}_j = \\max \\{ f_i \\mid (j-1)l < i \\le \\min(jl, n) \\} $.  \nThen:  \n$$\n\\text{width}(l) = \\sum_{j=1}^{c} \\text{col}_j + (c - 1)\n$$\n\n**Constraints**  \n1. $ 1 \\le n \\le 10^5 $  \n2. $ 1 \\le w \\le 10^9 $  \n3. $ 1 \\le f_i \\le w $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFind the minimal $ l \\in \\{1, 2, \\dots, n\\} $ such that:  \n$$\n\\sum_{j=1}^{\\lceil n/l \\rceil} \\max_{i \\in I_j} f_i + \\left( \\left\\lceil \\frac{n}{l} \\right\\rceil - 1 \\right) \\le w\n$$  \nwhere $ I_j = \\{ (j-1)l + 1, \\dots, \\min(jl, n) \\} $.","simple_statement":"Given n filenames with known lengths and a screen width w, find the minimum number of lines l such that when the filenames are displayed in a multi-column format (sorted lexicographically, filled row by row), the total width of each row does not exceed w.","has_page_source":false}