题目描述

有 $n$ 袋干草，第 $i$ 袋干草的重量是 $w[i]$。奶牛 Bessieb当前的快乐值是 $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 \le n \le 100$, $1 \le s \le 10000$, $0 \le t \le 100$ )。

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

提示

有 50% 的数据，$n \le 10$。

输出格式

一个整数。

样例

4 1234 0
10 20 30 40

100

3 100 0
100 100 100

100

5 101 2
100 100 100 100 100

400