题目内容

影像档案室要把一批胶片按卷号送进冲印线。一共有 $p$ 卷，编号从 $0$ 到 $p-1$，必须按编号从小到大连续处理，一卷胶片也不能拆到两天冲完。馆方把整批任务限制在 $d$ 天内结束。

主技师冲第 $i$ 卷需要 $g_i$ 分钟。为了避免某天严重加班、其余天却很空，排期时要压低主技师最忙那一天的时长。支援技师可以顶班：主技师每天最多把当天的 $q$ 卷整卷交给支援技师，这些卷完全不计入主技师耗时。馆方同时规定，主技师和支援技师每天最多工作 $480$ 分钟。

把这 $d$ 天里主技师单日耗时的最大值记为 $T$（支援技师冲掉的卷不计入）。请给出 $T$ 的最小值；若在上述规则下无法在 $d$ 天内做完，输出 -1。天数可以不满 $d$ 天。

输入描述

第一行三个整数 $p$、$d$、$q$，表示胶片卷数、可用天数、主技师每天最多可交接的卷数（$1\le p\le 2\times 10^4$，$1\le d\le 10^3$，$0\le q\le 10$）。

第二行 $p$ 个整数 $g_0,g_1,\ldots,g_{p-1}$（$1\le g_i\le 480$），表示主技师冲各卷所需分钟数。

输出描述

输出一个整数：主技师最忙日耗时 $T$ 的最小值（单位：分钟）。无法完成时输出 -1。

样例1

输入

3 2 1
40 80 90

输出

40

说明

每天最多交接 1 卷。

• 第一天处理第 0、1 卷（40、80），把 80 交给支援技师，主技师耗时 40。
• 第二天只处理第 2 卷（90），整卷交给支援技师，主技师耗时 0。

最忙日为 40。若第一天只冲第 0 卷，第二天留下 80 与 90，主技师至少还要自己冲 80，最忙日变成 80，更差。

样例2

输入

2 3 1
10 20

输出

0

说明

可用天数多于卷数。每天只冲一卷并交给支援技师，支援技师每天耗时不超过 480，主技师全程不干活，因此 $T=0$。

样例3

输入

3 1 2
300 250 200

输出

300

说明

只有 1 天，最多交接 2 卷。支援技师不能同时接走 300 与 250（和为 550，超过 480），但可以接走 250 与 200（和为 450），主技师只冲 300。

样例4

输入

2 1 0
300 200

输出

-1

说明

只有 1 天且不能交接。两卷合计 500 分钟，超过主技师每天 480 的上限，无法完成。

数据范围

• $1\le p\le 2\times 10^4$
• $1\le d\le 10^3$
• $0\le q\le 10$
• $1\le g_i\le 480$
• 所有输入均为整数