分数: 366 分
问题陈述
高桥正在参加在一条笔直的商店街上举行的宝石收集活动。有 N 街上的商店从左到右一字排开, i第店 (1 \leq i \leq N) 有 A_i 宝石放置在其中。
高桥开始在商店 S。根据赛事规则,高桥必须准确地做出 K 移动。他一举从当前的商店搬到了邻近的商店。也就是说,当他当前在商店时 p (1 \leq p \leq N),他可以移动到商店 p-1 if p-1 \geq 1,或前往商店 p+1 if p+1 \leq N。他不能走到商店的左边 1 或商店右侧 N。他可能会多次光顾同一家商店。
对于高桥访问的每个商店(包括商店 S 他开始的地方),他可以收集 A_i 宝石放在那里。然而,即使他多次访问同一家商店,他也只能在第一次访问时收集宝石。
确定高桥在精确制作时可以收集的最大宝石总数 K 移动。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq S \leq N
- 1 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N S K A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表店铺数量,整数 S 代表高桥的初始位置,一个整数 K 代表移动次数,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每个商店放置的宝石数量,以空格分隔。
输出
打印高桥在一行中可以收集的最大宝石总数。
示例输入 1
5 3 2 10 20 30 40 50
示例输出 1
120
示例输入 2
4 1 3 5 100 1 10
示例输出 2
116
示例输入 3
12 6 8 3 15 8 20 7 50 6 12 30 4 25 10
示例输出 3
144
示例输入 4
30 17 25 12 0 45 23 78 5 90 34 11 67 8 56 100 3 29 74 41 62 18 95 7 36 84 21 50 69 14 88 2 31
示例输出 4
922
示例输入 5
2 1 1000000000 1000000000 0
示例输出 5
1000000000