题目描述

码头到了一批货物，一共 $n$ 件，第 $i$ 件的体积为 $w_i$。仓库里备好了 $m$ 个规格完全相同的集装箱，每个箱子的容量都是 $C$。

装卸工只能把每件货物整件放进某一个集装箱，不允许拆开。现在想挑一个尽量小的容量 $C$，使得所有货物都能被装进这 $m$ 个箱子里。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $w_1,w_2,\dots,w_n$。

输出格式

一行一个整数，表示最小的 $C$。

输入输出样例 #1

输入 #1

5 2
7 3 5 2 8

输出 #1

13

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 30$，$1\le m\le 10$，$1\le w_i\le 10^9$。体积和可能到 $3\times 10^{10}$。