二分答案：不会求，那就猜一个再验证

// 数列分段：最大值最小化 —— 暴力：把答案从小到大挨个试
//
// 输入：第一行 n m（n 个数，要分成 m 段）
//       第二行 n 个正整数
// 输出：一个整数 —— 在所有「把数列切成 m 段连续子段」的方案里，
//       「每段和的最大值」最小能是多少
//
// 例：4 3 / 1 5 2 4  →  答案 6
//     切成 [1 5] [2] [4]，三段的和分别是 6、2、4，最大值 6。
//     再也找不到更小的了。
//
// ============ 这一章的核心动作 ============
//
// 「怎么切才最优」很难直接想。但换一个问法，事情立刻简单了：
//
//     **给定一个上限 x，能不能把数列切成不超过 m 段、且每段和都 <= x？**
//
// 这个问题好回答：从左往右贪心地装，装不下就开新的一段，数一数用了几段。
//   用的段数 <= m  →  x 可行
//   用的段数 >  m  →  x 太小了
//
// 于是「求答案」变成了「验证一个猜测」。而验证比求解简单一百倍。
//
// 这份暴力就是：从最小的可能答案开始，一个一个往上试，第一个能通过验证的就是答案。
// 复杂度 O(答案范围 × n) —— 答案范围可以到所有数之和，所以它很慢。
// 正解只改一件事：把「一个一个试」换成「二分着试」。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

/**
 * 能不能让每段和都不超过 limit，并且段数不超过 m ？
 *
 * 贪心：从左往右能装就装，装不下就另起一段。
 * 为什么贪心是对的：当前这段能多装一个就多装一个，绝不会让后面变难 ——
 * 少装一个只会让后面剩下更多东西，段数只可能更多，不可能更少。
 */
bool ok(long long limit) {
    int seg = 1;                      // 至少一段
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > limit) return false;      // 单个数就超了，怎么切都不行
        if (cur + a[i] <= limit) {
            cur += a[i];              // 塞进当前这段
        } else {
            seg++;                    // 装不下，另起一段
            cur = a[i];
        }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    a.assign(n + 1, 0);

    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    // 答案不可能小于「最大的那个数」（它总得待在某一段里），
    // 也不可能大于「所有数之和」（那是只分一段的情况）。
    for (long long x = mx; ; x++) {
        if (ok(x)) { cout << x << "\n"; break; }
        if (x > sum) { cout << sum << "\n"; break; }   // 兜底，正常走不到这里
    }
    return 0;
}

// 数列分段：最大值最小化 —— 二分答案
//
// 输入输出和 brute.cpp 完全一样。
// **`ok()` 函数一个字都没改**，改的只有「怎么找那个答案」。
//
// 为什么能二分？因为可行性是**单调**的：
//
//     x 太小 → 不可行     x 够大 → 可行
//     ✗ ✗ ✗ ✗ ✗ ✗ | ✓ ✓ ✓ ✓ ✓ ✓ ✓
//                  ↑
//              我们要的就是这条分界线上的第一个 ✓
//
//   如果 x 可行（能切成 ≤ m 段），那 x+1 更宽松，一定也可行。
//   所以整条数轴一定是「一段 ✗ 接一段 ✓」，中间只有一个分界点。
//
// 这正是第 8 章说的二分的真正条件：**不是「有序」，是「存在分界点」。**
// 于是第 8 章那个模板原封不动搬过来，只把 check 换成 ok()：
//
//     l = 最小可能答案, r = 最大可能答案
//     while (l < r) { mid = l + (r-l)/2; if (ok(mid)) r = mid; else l = mid + 1; }
//
// 复杂度 O(n log sum)。sum 就算是 10^14，log 也只有 47。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    a.assign(n + 1, 0);

    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    // 二分的范围要「一定包含答案」：
    //   下界 mx  —— 最大的那个数总得待在某一段里，所以答案不可能比它小
    //   上界 sum —— 只分一段时就是全部之和，答案不可能比它大
    long long l = mx, r = sum;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (ok(mid)) r = mid;          // mid 可行 → 答案在 mid 或更小
        else l = mid + 1;              // mid 不可行 → 答案更大
    }

    cout << l << "\n";
    return 0;
}

// 二分答案 —— 把「猜一个 → 验证」的全过程打印出来
//
// 输入：n m / n 个正整数（用小数据）
// 输出：先把每一个候选答案的可行性列成一张表（✗✗✗✓✓✓），
//       再演示二分是怎么在这张表上找到那条分界线的
//
// 那张表是这一章最值得看的东西：
//   **它一定是「左边一片 ✗、右边一片 ✓」，中间只有一个分界点。**
//   有了这个形状，二分才成立。
//
// 每次做二分答案的题，都应该先在脑子里（或者纸上）确认这个形状。
// 确认不了，说明可行性不单调，那就不能二分。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

bool ok(long long limit, bool verbose = false) {
    int seg = 1;
    long long cur = 0;
    string detail = "[";
    for (int i = 1; i <= n; i++) {
        if (a[i] > limit) {
            if (verbose) cout << "      单个数 " << a[i] << " 就超过上限了，直接不行\n";
            return false;
        }
        if (cur + a[i] <= limit) { cur += a[i]; detail += to_string(a[i]) + " "; }
        else { seg++; cur = a[i]; detail += "| " + to_string(a[i]) + " "; }
    }
    detail += "]";
    if (verbose) {
        cout << "      贪心地装：" << detail << "  用了 " << seg << " 段，"
             << (seg <= m ? "不超过 " : "超过了 ") << m << " → " << (seg <= m ? "可行 ✓" : "不可行 ✗") << "\n";
    }
    return seg <= m;
}

int main() {
    if (!(cin >> n >> m)) return 0;
    if (n <= 0 || n > 12) { cout << "这份是用来看过程的，请用 1 <= n <= 12\n"; return 0; }

    a.assign(n + 1, 0);
    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    cout << "数列：";
    for (int i = 1; i <= n; i++) cout << a[i] << " ";
    cout << "　　要分成不超过 " << m << " 段\n";
    cout << "答案一定在 [" << mx << ", " << sum << "] 里（下界 = 最大的那个数，上界 = 全部之和）\n\n";

    cout << "把每个候选答案的可行性列出来：\n  ";
    long long firstOk = -1;
    for (long long x = mx; x <= sum; x++) {
        bool r = ok(x);
        if (r && firstOk < 0) firstOk = x;
        cout << x << (r ? "✓ " : "✗ ");
    }
    cout << "\n\n  看这一行的形状：左边一片 ✗，右边一片 ✓，中间只有一个分界点 —— 就是 "
         << firstOk << "。\n  「有这个形状，才能二分」。\n\n";

    cout << "二分是这样找到它的：\n";
    long long l = mx, r = sum;
    int step = 0;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        cout << "  第 " << ++step << " 轮：候选范围 [" << l << ", " << r << "]，猜 mid = " << mid << "\n";
        bool good = ok(mid, true);
        if (good) { cout << "      → 可行，答案不会更大，r = mid = " << mid << "\n"; r = mid; }
        else { cout << "      → 不可行，答案只能更大，l = mid + 1 = " << (mid + 1) << "\n"; l = mid + 1; }
    }

    cout << "\n答案 = " << l << "　（只用了 " << step << " 轮验证，而逐个试要试 "
         << (firstOk - mx + 1) << " 次）\n";
    return 0;
}

// 数列分段：最大值最小化 —— 二分答案
//
// 输入输出和 brute.cpp 完全一样。
// **`ok()` 函数一个字都没改**，改的只有「怎么找那个答案」。
//
// 为什么能二分？因为可行性是**单调**的：
//
//     x 太小 → 不可行     x 够大 → 可行
//     ✗ ✗ ✗ ✗ ✗ ✗ | ✓ ✓ ✓ ✓ ✓ ✓ ✓
//                  ↑
//              我们要的就是这条分界线上的第一个 ✓
//
//   如果 x 可行（能切成 ≤ m 段），那 x+1 更宽松，一定也可行。
//   所以整条数轴一定是「一段 ✗ 接一段 ✓」，中间只有一个分界点。
//
// 这正是第 8 章说的二分的真正条件：**不是「有序」，是「存在分界点」。**
// 于是第 8 章那个模板原封不动搬过来，只把 check 换成 ok()：
//
//     l = 最小可能答案, r = 最大可能答案
//     while (l < r) { mid = l + (r-l)/2; if (ok(mid)) r = mid; else l = mid + 1; }
//
// 复杂度 O(n log sum)。sum 就算是 10^14，log 也只有 47。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    a.assign(n + 1, 0);

    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    // 二分的范围要「一定包含答案」：
    //   下界 mx  —— 最大的那个数总得待在某一段里，所以答案不可能比它小
    //   上界 sum —— 只分一段时就是全部之和，答案不可能比它大
    long long l = mx, r = sum;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (ok(mid)) r = mid;          // mid 可行 → 答案在 mid 或更小
        else l = mid + 1;              // mid 不可行 → 答案更大
    }

    cout << l << "\n";
    return 0;
}

// 数列分段：最大值最小化 —— 二分答案
//
// 输入输出和 brute.cpp 完全一样。
// **`ok()` 函数一个字都没改**，改的只有「怎么找那个答案」。
//
// 为什么能二分？因为可行性是**单调**的：
//
//     x 太小 → 不可行     x 够大 → 可行
//     ✗ ✗ ✗ ✗ ✗ ✗ | ✓ ✓ ✓ ✓ ✓ ✓ ✓
//                  ↑
//              我们要的就是这条分界线上的第一个 ✓
//
//   如果 x 可行（能切成 ≤ m 段），那 x+1 更宽松，一定也可行。
//   所以整条数轴一定是「一段 ✗ 接一段 ✓」，中间只有一个分界点。
//
// 这正是第 8 章说的二分的真正条件：**不是「有序」，是「存在分界点」。**
// 于是第 8 章那个模板原封不动搬过来，只把 check 换成 ok()：
//
//     l = 最小可能答案, r = 最大可能答案
//     while (l < r) { mid = l + (r-l)/2; if (ok(mid)) r = mid; else l = mid + 1; }
//
// 复杂度 O(n log sum)。sum 就算是 10^14，log 也只有 47。

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<long long> a;

bool ok(long long limit) {
    int seg = 1;
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > limit) return false;
        if (cur + a[i] <= limit) cur += a[i];
        else { seg++; cur = a[i]; }
    }
    return seg <= m;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    a.assign(n + 1, 0);

    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) { cin >> a[i]; sum += a[i]; mx = max(mx, a[i]); }

    // 二分的范围要「一定包含答案」：
    //   下界 mx  —— 最大的那个数总得待在某一段里，所以答案不可能比它小
    //   上界 sum —— 只分一段时就是全部之和，答案不可能比它大
    long long l = mx, r = sum;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (ok(mid)) r = mid;          // mid 可行 → 答案在 mid 或更小
        else l = mid + 1;              // mid 不可行 → 答案更大
    }

    cout << l << "\n";
    return 0;
}