P5892 [IOI 2014] holiday 假期

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

无

无

**子任务** 在所有的子任务中，有 $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$ | 无限制 |