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

题目背景

小玫在MC存档里修了一条路，这条路有$n$个路段，各个路段经过苦力怕的摧残，都遭到了不同程度的破坏，但是小玫赶时间去看IEM科隆Major，所以他没时间修复这条路，只能在这条路上修建几个临时补给站。

说明

给定三个整数$n、m、s$，分别代表这条路有$n$个路段、可以修建$m$个临时补给站以及小玫的饱食度上限。

接下来给定一个数组$r$，第$i$个数$r_i$代表走过这个路段需要消耗多少饱食度。

你可以在任意两条路中间修建一个临时补给站，每经过一个临时补给站，小玫的饱食度都会补满（达到上限），小玫希望他饱食度最低的时候饱食度尽量高，即走过这整条路，使他在整个过程中的最小饱食度尽可能大，你需要输出这个尽可能大的最小饱食度。

输入格式

第一行三个整数$n、m、s$，分别代表这条路的段数、最多修建临时补给站的数量以及小玫的饱食度上限。

第二行$n$个数$r_1...r_n$，分别代表走过第$i$段路需要消耗多少饱食度

输出格式

一行一个整数，代表整个过程中尽可能大的最低饱食度

样例

6 2 1000
15 12 13 6 8 19

973

数据范围

$对于20\%的数据：0\le m < n,r_i \le 100$。
$对于100\%的数据：0\le m < n,r_i\le 10^5, s\le 10^{11}$。
保证整个过程中小玫的饱食度$\geq 0$，初始时饱食度为$s$。