BN202601 均衡分装

题目描述

小明有 N 箱货物，它们已经按照编号排成一排，第 i 箱货物的重量为 a_i 千克。

现在要把这些货物依次分给 K 辆货车。每辆车装的货物必须是连续的一段，并且每辆车至少装一箱货物。

请你计算：在合理分配的情况下，所有车辆中装载重量最大的车辆，其重量最少是多少。

输入格式

第一行包含两个正整数 N 和 K，分别表示货物箱数和货车数量。

第二行包含 N 个正整数 a_1, a_2, ..., a_N，表示每箱货物的重量。

输出格式

输出一个整数，表示所有车辆中最大装载重量的最小值。

样例输入

5 2
2 5 3 4 6

样例输出

10

样例说明

一种最优分配方式如下：

第 1 辆车：2 5 3，总重量为 10
第 2 辆车：4 6，总重量为 10

所有车辆中最大的装载重量为 10，并且不存在一种分配方式，使这个最大值小于 10。

数据范围

• 1 ≤ K ≤ N
• 1 ≤ N ≤ 10^5
• 1 ≤ a_i ≤ 10^9