该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某运输系统需要处理 $N$ 根长度不同的材料。第 $i$ 根材料的长度为 $A_i$。

运输设备规定，每一段材料的长度都不能超过某个正整数 $L$。如果某段材料的长度大于 $L$，就必须在运输前将其切割成更短的若干段。

每进行一次切割，可以选取当前的一段材料，将其分成两段，并且需要满足：

• 两段材料的长度均为正整数；
• 两段材料的长度之和等于切割前材料的长度。

例如，一根长度为 $7$ 的材料可以通过一次切割分成长度为 $3$ 和 $4$ 的两段。

整个处理过程中，最多允许进行 $K$ 次切割。

请你求出最小的正整数 $L$，使得能够在总切割次数不超过 $K$ 的条件下，将所有材料处理为长度均不超过 $L$ 的若干段。

输入格式

第一行输入两个整数 $N,K$，分别表示原始材料的数量和允许进行的最大切割次数。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，其中 $A_i$ 表示第 $i$ 根材料的长度。

输出格式

输出一行一个正整数，表示满足条件的最小值 $L$。

1 1
5

3

2 3
9 6

3

数据范围

• 对于 $10$ 的数据，$1 \le N \le 100$，$0 \le K \le 3$，$1 \le A_i \le 10^3$。
• 对于 $50$ 的数据，$1 \le N \le 10^3$，$0 \le K \le 10^5$，$1 \le A_i \le 10^5$。
• 对于 $100$ 的数据，$1 \le N \le 10^6$，$0 \le K \le 10^9$，$1 \le A_i \le 10^9$。