← 返回题目列表

Codeforces · 1614/A

A. 沙发椅和商店

中文机器翻译题面 查看原题

商人迪万喜欢巧克力!今天他来到一家商店买巧克力。和所有商人一样,迪万知道金钱的价值,所以他不会买太贵的巧克力。同时,太便宜的巧克力味道不好,他也不会买。

他来到的商店有$$$n$$$种不同的巧克力棒,第$$$i$$$块巧克力棒的价格是$$$a_i$$$美元。 Divan 认为,如果一块巧克力的价格严格超过 $$$r$$$ 美元,那么它就太贵了。同样,如果一块巧克力的价格严格低于 $$$l$$$ 美元,他认为它太便宜了。 Divan不会买太便宜或太贵的金条。

Divan 不会把他所有的钱都花在巧克力棒上,所以他最多会花 $$$k$$$ 美元买巧克力。

请确定 Divan 可以购买的巧克力棒的最大数量。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的描述由两行组成。第一行包含整数 $$$n$$$, $$$l$$$, $$$r$$$, $$$k$$$ ($$$1 \le n \le 100$$$, $$$1 \le l \le r \le 10^9$$$, $$$1 \le k \le 10^9$$$) - 巧克力的最低可接受价格、巧克力的最高可接受价格和 Divan 的总价预算,分别。

第二行包含一个序列 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) 整数 - 商店中巧克力棒的价格。

输出

对于每个测试用例,打印一个整数 - Divan 可以购买的巧克力棒的最大数量。

示例

输入 #1

8
3 1 100 100
50 100 50
6 3 5 10
1 2 3 4 5 6
6 3 5 21
1 2 3 4 5 6
10 50 69 100
20 30 40 77 1 1 12 4 70 10000
3 50 80 30
20 60 70
10 2 7 100
2 2 2 2 2 7 7 7 7 7
4 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1000000000
1 1 1 1
1

输出 #1

2
2
3
0
0
10
1
1

注意

在第一个示例中,Divan 可以购买巧克力棒 $$$1$$$ 和 $$$3$$$ 并花费 $$$100$$$ 购买它们。

在第二个示例中,Divan 可以购买巧克力棒 $$$3$$$ 和 $$$4$$$ 并花费 $$$7$$$ 购买它们。

在第三个示例中,Divan 可以以 $$$12$$$ 美元购买巧克力棒 $$$3$$$、$$$4$$$ 和 $$$5$$$。

在第四个示例中,Divan 无法购买任何巧克力棒,因为它们要么太便宜,要么太贵。

在第五个示例中,Divan 无法购买任何巧克力棒,因为他认为第一块巧克力太便宜,并且没有第二块或第三块巧克力的预算。

在第六个示例中,Divan 可以购买商店中的所有巧克力棒。