[IOI2014] holiday 假期

题目描述

健佳正在制定下个假期去台湾的游玩计划。在这个假期,健佳将会在城市之间奔波,并且参观这些城市的景点。 在台湾共有 $n$ 个城市,它们全部位于一条高速公路上。这些城市连续地编号为 $0$ 到 $n-1$。 对于城市 $i$($0 < i < n-1$ )而言,与其相邻的城市是 $i-1$ 和 $i+1$。但是对于城市 $0$,唯一与其相邻的是城市 $1$。而对于城市 $n-1$,唯一与其相邻的是城市 $n-2$。 每个城市都有若干景点。健佳有 $d$ 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天,健佳可以选择去一个相邻的城市,或者参观所在城市的所有景点,但是不能同时进行。即使健佳在同一个城市停留多次,他也不会去重复参观该城市的景点。请帮助健佳策划这个假期,以便能让他参观尽可能多的景点。

输入输出格式

输入格式


- 第 $1$ 行:有三个非负整数, $n$ 代表城市数目,$start$ 代表起点城市编号,$d$ 代表假期天数。 - 第 $2$ 行:$n$ 个非负整数 $a[0],\cdots, a[n-1]$,对于 $0 \le i \le n-1$,$a[i]$ 代表城市 $i$ 的景点数目。

输出格式


- 共一行,最多参观的景点数目。

输入输出样例

输入样例 #1

5 2 7
10 2 20 30 1

输出样例 #1

60

说明

**子任务** 在所有的子任务中,有 $0 \le d \le 2n+floor(n/2)$。 而且,每个城市中的景点数都是非负整数。 | 子任务 | 分值 | $n$ | 各城市景点数的最大值 | 起点城市 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $7$ | $2 \le n \le 20$ | $10^9$ | 无限制 | | $2$ | $23$ | $2 \le n \le 10^5$ | $100$ | 城市 $0$ | | $3$ | $17$ | $2 \le n \le 3 \times 10 ^3$ | $10^9$ |无限制 | | $4$ | $53$ | $2 \le n \le 10^5$ | $10^9$ | 无限制 |