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

在台湾共有 $n$ 个城市，它们全部位于一条高速公路上。这些城市连续地编号为 $0$ 到 $n-1$。对于城市 $i$ ($0<i<n-1$) 而言，与其相邻的城市是 $i-1$ 和 $i+1$。但是对于城市 $0$，唯一与其相邻的是城市 $1$。而对于城市 $n-1$，唯一与其相邻的是城市 $n-2$。

每个城市都有若干景点。健佳有 $d$ 天假期并且打算要参观尽量多的景点。健佳已经选择了假期开始要到访的第一个城市。在假期的每一天，健佳可以选择去一个相邻的城市，或者参观所在城市的所有景点，但是不能同时进行。即使健佳在同一个城市停留多次，他也不会去重复参观该城市的景点。请帮助健佳策划这个假期，以便能让他参观尽可能多的景点。

任务

请实现函数 findMaxAttraction，以计算健佳最多可以参观多少个景点。

• findMaxAttraction(n, start, d, attraction)
  • $n$: 城市数。
  • start: 起点城市的编号。
  • $d$: 假期的天数。
  • attraction: 长度为 $n$ 的数组；attraction[i] 表示城市 $i$ 的景点数目，其中 $0\le i\le n-1$。
  • 该函数应返回健佳最多可以参观的景点数。

子任务

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

实现细节

本题只支持 C/C++。

你只能提交一个源文件实现上述的函数，其命名与接口需遵循下面的要求。你还要在该文件中包含头文件holiday.h。

注意，计算的结果可能会很大，所以函数 findMaxAttraction 的返回值类型是一个64位整数。

long long int findMaxAttraction(int n, int start, int d, int attraction[]);

评测方式

评测系统需要读入如下格式的输入数据:

• 第 $1$ 行: $n$, start, $d$。
• 第 $2$ 行: $\text{attraction[0]},\dots ,\text{attraction[n-1]}$。

评测系统将会输出 findMaxAttraction 的返回值。

交互式类型的题目怎么本地测试

时间限制：$5\mathtt{\text{s}}$

空间限制：$64\mathtt{\text{MB}}$

下载

样例及测评库下载