Minimize Shelf Width

You are given a sequence of books with various widths and a fixed number of shelves. Your task is to arrange the books, in the given order, into the shelves such that the maximum total width of any shelf is minimized.

Formally, given an array of integers \(books = [b_1, b_2, \ldots, b_n]\) and an integer \(S\) representing the number of shelves, you need to partition the array into \(S\) contiguous segments. The width of a shelf is defined as the sum over books placed on that shelf. The goal is to minimize \(\max_{1 \leq i \leq S} (\text{sum of books in shelf } i)\).

For example, if the books are [1, 2, 3, 4, 5, 6, 7, 8, 9] and there are 3 shelves, one possible partition is [1,2,3,4,5], [6,7], [8,9] with shelf widths 15, 13, and 17, respectively, and the minimum possible maximum shelf width is 17.

inputFormat

The input is read from standard input (stdin) and has the following format:

1. The first line contains two integers \(N\) and \(S\), where \(N\) is the number of books and \(S\) is the number of shelves.
2. The second line contains \(N\) integers representing the widths of the books.

outputFormat

Output a single integer denoting the minimum possible value of the maximum shelf width when the books are arranged optimally. The output should be printed to standard output (stdout).

9 3
1 2 3 4 5 6 7 8 9

17