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

题目描述

你有 $n$ 个任务，第 $i$ 个任务的工作量为一个整数 $a_i$。你需要在 $m$ 天内完成所有任务。为此，你需要将任务序列分成 $m$ 个连续的工作段，每天按顺序完成一段。

每天，你可以选择当天工作段内的至多一个任务进行加速，使其工作量变为 $\lfloor \frac{a_i}{2} \rfloor$。每天的工作量为当天工作段内所有任务工作量之和。

你需要找到一个最小非负整数 $c$，使得存在一种分段和加速的方案，满足每天的工作量都不超过 $c$。

容易证明，一定有解。

输入格式

第 $1$ 行一个正整数 $n, m$，分别表示任务数量和工作天数。

第 $2$ 行 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示每个任务的工作量。

输出格式

一行，一个非负整数 $c$，含义如题所示。

5 3
2 3 9 4 7

7

7 4
12 3 8 19 6 1 15

14

说明/提示

【数据范围】

对于 $40\%$ 的测试数据，$1 \le n \le 18$，$1 \le a_i \le 50$。

对于 $60\%$ 的测试数据，$1 \le n \le 5000$。

对于 $100\%$ 的测试数据，$1 \le n \le 2 \times 10^5$，$1 \le a_i \le 10^9$。