旷课大师
题号：NC292227
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}鲁路修虽然是一个学生，但正忙于他开万世太平的大事业，因此需要经常外出。然而，他每次逃课都会引起老师的警觉。
\hspace{15pt}具体地来说，在接下来的 n 天内，为了完成他的任务，鲁路修的出勤天数不超过 k 天。
\hspace{15pt}初始时老师对他的怀疑值是 0，如果他在第 i 天缺席，老师的怀疑值就会增加 a_i，否则就不增加。

\hspace{15pt}在开始任务之前，鲁路修可以从 CC 那里选取一个超能力：
\hspace{23pt}\bullet\,如果他选择超能力一，则每次鲁路修出勤时，当前老师的怀疑值之和就会减半（向下取整）。
\hspace{23pt}\bullet\,如果他选择超能力二，则在每一次鲁路修出勤时，他都可以使用 geass，让老师从当天算起，共 m 天里，都默认他出勤（也就是说，不管他出不出勤，老师的怀疑值都不增加）。
\hspace{15pt}注意，他在选择了能力后就不能再更改。

\hspace{15pt}鲁路修希望合理规划他的出勤，使得在这 n 天内老师的「怀疑值的最大值」最小。请你输出这个最小值。

输入描述:

\hspace{15pt}第一行输入三个整数 n,k,m \left( k,m\le n \le 3\times 10^3\right)。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \cdots, a_n \left( 1 \le a_i \le 10^9 \right)。

输出描述:

\hspace{15pt}输出一个整数，代表这 n 天内老师的「怀疑值的最大值」最小是多少。
示例1

输入

复制 
11 1 4
1 1 4 5 1 4 1 9 1 9 1

输出

复制 
17

说明

\hspace{15pt}在这个样例中，其中一种最优的方案是，选择超能力二。只在第 7 天出勤，且使用 geass 让老师在第 7,8,9,10 天都默认他出勤。这样一来，老师「怀疑值的最大值」即为最后一天的怀疑值，前六天与最后一天增量之和，即 1+1+4+5+1+4+1=17。
示例2

输入

复制 
5 1 3
7 1 1 7 7

输出

复制 
8

备注: