Antler Archive

# Antler Archive ## Problem Bessie is organizing the MOOSACO archive of antler documents. She has $N$ shelves in a row, and each shelf has a certain weight. She wants to pack these shelves into at most $K$ consecutive crates such that the maximum weight of any single crate is minimized. Each crate must contain at least one shelf, and shelves must be placed into crates in order (a crate cannot skip shelves). The weight of a crate is the sum of the weights of all shelves it contains. Find the minimum possible value of the maximum crate weight. ## Input The first line contains two integers $N$ and $K$ ($1 \le K \le N \le 10^5$). The second line contains $N$ integers $w_1, w_2, \ldots, w_N$ ($1 \le w_i \le 10^9$), the weights of the shelves. ## Output Print a single integer: the minimum possible maximum weight of any crate. ## Constraints - $1 \le K \le N \le 10^5$ - $1 \le w_i \le 10^9$ - The answer always fits in a 64-bit integer. ## Sample **Input:** ``` 5 2 7 2 5 10 8 ``` **Output:** ``` 18 ``` **Explanation:** Bessie can split the shelves into two crates: the first crate contains shelves with weights $[7, 2, 5]$ (total weight 14) and the second crate contains shelves with weights $[10, 8]$ (total weight 18). The maximum weight is 18, which is optimal.