{"problem":{"name":"Minimum Width","description":{"content":"Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$\\-th word $(1\\leq i\\leq N)$ is $L _ i$. The words are displayed in the window sep","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc319_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi is displaying a sentence with $N$ words in a window. All words have the same height, and the width of the $i$\\-th word $(1\\leq i\\leq N)$ is $L _ i$.\nThe words are displayed in the window separated by a space of width $1$. More precisely, when the sentence is displayed in a window of width $W$, the following conditions are satisfied.\n\n*   The sentence is divided into several lines.\n*   The first word is displayed at the beginning of the top line.\n*   The $i$\\-th word $(2\\leq i\\leq N)$ is displayed either with a gap of $1$ after the $(i-1)$\\-th word, or at the beginning of the line below the line containing the $(i-1)$\\-th word. It will not be displayed anywhere else.\n*   The width of each line does not exceed $W$. Here, the width of a line refers to the distance from the left end of the leftmost word to the right end of the rightmost word.\n\nWhen Takahashi displayed the sentence in the window, the sentence fit into $M$ or fewer lines. Find the minimum possible width of the window.\n\n## Constraints\n\n*   $1\\leq M\\leq N\\leq2\\times10 ^ 5$\n*   $1\\leq L _ i\\leq10^9\\ (1\\leq i\\leq N)$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$L _ 1$ $L _ 2$ $\\ldots$ $L _ N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc319_d","tags":[],"sample_group":[["13 3\n9 5 2 7 1 8 8 2 1 5 2 3 6","26\n\nWhen the width of the window is $26$, you can fit the given sentence into three lines as follows.\n![image](https://img.atcoder.jp/abc319/710c42acf58eacf40178e28a0a0b3a2c.png)\nYou cannot fit the given sentence into three lines when the width of the window is $25$ or less, so print $26$.\nNote that you should not display a word across multiple lines, let the width of a line exceed the width of the window, or rearrange the words.\n![image](https://img.atcoder.jp/abc319/ed3aac3d0c0eb00c5663aa6a95023b33.png)"],["10 1\n1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000","10000000009\n\nNote that the answer may not fit into a $32\\operatorname{bit}$ integer."],["30 8\n8 55 26 97 48 37 47 35 55 5 17 62 2 60 23 99 73 34 75 7 46 82 84 29 41 32 31 52 32 60","189"]],"created_at":"2026-03-03 11:01:14"}}