Migrated from Lutece 2795 大运会爪巴

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

受大运会影响，ljj 的报告全都堆在了一起。

今天他终于把报告都写完了，他要前往 $n$ 个机房交报告，这 $n$ 个机房从左到右排成一行，机房编号范围是 0 到 n-1， 第 $i$ 个机房与第 $i-1$ 和第 $i+1$ 个机房相邻，但第 0 个机房只和第 1 个机房相邻，第 $n-1$ 个机房只和第 $n-2$ 个机房相邻。报告只能在指定的机房上交，我们可以考虑成每个机房有 $a_{i}$ 个报告要交。

由于 ljj 下午才赶完报告，距离机房关门剩下的时间不多了。现在还剩下 $T$ 分钟留给 ljj 交报告，ljj 现在所在的机房是 $S$，每分钟 ljj 可以动身前往一个相邻的机房，也可以选择在当前机房打开电脑交报告（可以在1分钟内把当前机房要交的所有报告都交上去），但是二者不能在 1 分钟内同时进行。现在问 ljj 最多能在机房关门前交多少篇报告。因为 ljj 忙着交报告，于是他求助你解决这个问题。

Input

第一行读入三个正整数 $n,S,T$ ，分别表示机房数，起始地点和剩余时间

第二行读入 $n$ 个正整数，第 $i$ 个整数 $a_{i}$ 表示第 $i$ 个机房要交的报告数

Output

一行，表示最多能交的报告数

Samples

8 3 10
10 5 6 18 9 17 6 3

56

20 6 19
10 5 31 10 50 60 19 2 5 46 26 15 17 81 92 64 57 10 39 50

426

Constraints

$n\le 10^{5},0\le S\le n-1, a_{i}\le 10^{9},0\le T\le 2n+\lfloor{\frac{n}{2}}\rfloor$

Note

大运会爪巴

Resources

2022 UESTC ICPC Training for Dynamic Programming