You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

促销

题目描述

WFYZ商店里有$n$件商品，每件商品有价格 $c_i$，商店正在做促销活动，可以一次买$k$件商品且只需要花费这$k$件商品里价格最高的商品的价格的$2$倍。 小容只有$p$元，他最多能买多少件商品?

输入格式

第一行三个整数$n, p, k$，分别表示商品数量，小容的钱数以及促销中的$k$。 第二行$n$个整数表示每个商品的价格。

输出格式

一行一个整数表示小容可以购买商品的最大件数。

样例 #1

样例输入 #1

5 6 2
2 4 3 5 7

样例输出 #1

2

样例 #2

样例输入 #2

5 11 4
2 4 3 5 7

样例输出 #2

4

样例 #3

样例输入 #3

2 999 2
1000 1000

样例输出 #3

0

提示

对于$20\%$ 的数据，保证 $k ≤ 2$

对于另外 $20\%$的数据，保证$n ≤ 20$

对于另外 $20\%$ 的数据，保证 $n ≤ 1000$

对于全部的数据，保证$1 ≤ n ≤ 2 × 10^5$ ,$1 ≤ p ≤ 2 × 10^9 ,1 ≤ k ≤ n,1 ≤ a_i ≤ 10^9$