#include <stdio.h>

int main() {
    int list[9] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = 9;
    int k = 3;
    int low,high;
    low = 9;
    high = 45;
    int result = 0;

    while (low <= high) {
        int mid = (low + high) / 2;

        int count = 1;
        int sum = 0;

        for (int i = 0; i < n; i++) {
            if (sum + list[i] > mid) {
                count++;
                sum = list[i];
            } else {
                sum += list[i];
            }
        }

        if (count <= k) {
            result = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    printf("%d ",result);
    
}