题目描述

有n袋干草，第i袋干草的重量是w[i]。奶牛bessie当前的快乐值是0，bessie希望它的快乐值至少要达到s。

如果奶牛吃掉第i袋干草，奶牛的快乐值会增加w[i]。

对于一袋干草来说，bessie要么整袋吃掉，要么不吃，不能吃这袋干草的一部分。

如果bessie当前的快乐值小于s，那么bessie必须要继续挑选干草吃。

bessie最近的感知功能不是很好，有一个延迟参数t。

如果t等于0，那么奶牛当前快乐值只要不小于s，那么它就不再吃干草了。

如果t是正整数，那么奶牛快乐值达到s以后，仍然要额外多吃t袋干草。

求奶牛bessie吃干草能获得的快乐值的最大值是多少。 注意：有可能bessie吃完所有的干草后，快乐值仍然没达到s。

输入格式

第一行，三个整数: n, s, t。1<=n<=100, 1<=s<=10000, 0<=t<=100。

第二行，n个正整数，第i个整数是w[i]。 所有w[i]的总和不超过1000000000。

【提示】

有50%的数据，n<=10。

输出格式

一个整数。

输入/输出例子1

输入：

4 1234 0
10 20 30 40

输出：

100

输入/输出例子2

输入：

3 100 0
100 100 100

输出：

100

输入/输出例子3

输入：

5 101 2
100 100 100 100 100

输出：

400