普及⏱ 1000ms💾 256MB#P5069

题目描述

包裹必须按给定顺序装船运输。船载重恒为 $W$,一天可以多次往返但每次装载按顺序连续装、总重不超过 $W$。求在 $days$ 天内送完全部包裹所需的最小船载重。

输入格式

第一行三个整数 $n$$days$?不——第一行两个整数 $n, days$;第二行 $n$ 个正整数重量。

输出格式

一行一个整数,即最小载重。

数据范围

$$1 \le days \le n \le 500,\ 1 \le w_i \le 500$$

样例输入 #1
1 1
1
样例输出 #1
1
样例输入 #2
5 1
1 2 3 4 5
样例输出 #2
15