题目描述

健佳正在制定下个假期去台湾的游玩计划。在这个假期，健佳将会在城市之间奔波，并且参观这些城市的景点。

在台湾共有 $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$ 的景点数目。

输出格式

• 共一行，最多参观的景点数目。

5 2 7
10 2 20 30 1

60

提示

子任务

在所有的子任务中，有 $0 \le d \le 2n+floor(n/2)$。 而且，每个城市中的景点数都是非负整数。