问题 AB: 粉丝小红

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:35 解决:10

题目描述

小红是某知名男团小明的狂热粉丝,该团某年七月要发行新专辑 ,小红得知消息后激动的托马斯全侧身旋转360度后空翻并劈了个叉,经过几个月的省吃俭用,小红手里存了W元钱,实体专辑分为N个版本,每个版本都非常好看,她无法取舍,但同时她又是个非常相信玄学的人,决定只购买她的幸运数字K本。
小红想在把手里的W元钱恰好花完的前提下自由选择购买哪一版专辑及其数量
已知购买第i版专辑花费i元钱并获得ai点甜蜜值,她想知道她可以获得的最大甜蜜值是多少
但小红数学考试经常不及格根本算不清楚,人美心善友爱大度乐于助人的你能帮帮小红吗?

输入

第一行三个整数N,K,W

第二行n个整数ai,ai表示用i元钱购买的专辑的甜蜜值

输出


输出小红能够获得的最大甜蜜值。

样例输入 复制

3 3 5
6 2 4

样例输出 复制

16

提示

小红可以分别选择用1元,1元,3元购买三张专辑,最大甜蜜值为6+6+4=16

2<=N,K<=2000, K<=W<=min(4000,2*K)
0<ai<=10000