codeforces#P1671C. Dolce Vita

    ID: 32890 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchbrute forcegreedymath*1200

Dolce Vita

Description

Turbulent times are coming, so you decided to buy sugar in advance. There are nn shops around that sell sugar: the ii-th shop sells one pack of sugar for aia_i coins, but only one pack to one customer each day. So in order to buy several packs, you need to visit several shops.

Another problem is that prices are increasing each day: during the first day the cost is aia_i, during the second day cost is ai+1a_i + 1, during the third day — ai+2a_i + 2 and so on for each shop ii.

On the contrary, your everyday budget is only xx coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding xx. Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.

Eventually, the cost for each pack will exceed xx, and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of test cases. Next tt cases follow.

The first line of each test case contains two integers nn and xx (1n21051 \le n \le 2 \cdot 10^5; 1x1091 \le x \le 10^9) — the number of shops and your everyday budget.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1091 \le a_i \le 10^9) — the initial cost of one pack in each shop.

It's guaranteed that the total sum of nn doesn't exceed 21052 \cdot 10^5.

For each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.

Input

The first line contains a single integer tt (1t10001 \le t \le 1000) — the number of test cases. Next tt cases follow.

The first line of each test case contains two integers nn and xx (1n21051 \le n \le 2 \cdot 10^5; 1x1091 \le x \le 10^9) — the number of shops and your everyday budget.

The second line of each test case contains nn integers a1,a2,,ana_1, a_2, \dots, a_n (1ai1091 \le a_i \le 10^9) — the initial cost of one pack in each shop.

It's guaranteed that the total sum of nn doesn't exceed 21052 \cdot 10^5.

Output

For each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.

Samples

输入数据 1

4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
1 1

输出数据 1

11
0
1
1500

Note

In the first test case,

  • Day 1: prices are [2,1,2][2, 1, 2]. You can buy all 33 packs, since 2+1+272 + 1 + 2 \le 7.
  • Day 2: prices are [3,2,3][3, 2, 3]. You can't buy all 33 packs, since 3+2+3>73 + 2 + 3 > 7, so you buy only 22 packs.
  • Day 3: prices are [4,3,4][4, 3, 4]. You can buy 22 packs with prices 44 and 33.
  • Day 4: prices are [5,4,5][5, 4, 5]. You can't buy 22 packs anymore, so you buy only 11 pack.
  • Day 5: prices are [6,5,6][6, 5, 6]. You can buy 11 pack.
  • Day 6: prices are [7,6,7][7, 6, 7]. You can buy 11 pack.
  • Day 7: prices are [8,7,8][8, 7, 8]. You still can buy 11 pack of cost 77.
  • Day 8: prices are [9,8,9][9, 8, 9]. Prices are too high, so you can't buy anything.
In total, you bought 3+2+2+1+1+1+1=113 + 2 + 2 + 1 + 1 + 1 + 1 = 11 packs.

In the second test case, prices are too high even at the first day, so you can't buy anything.

In the third test case, you can buy only one pack at day one.

In the fourth test case, you can buy 22 packs first 500500 days. At day 501501 prices are [501,501][501, 501], so you can buy only 11 pack the next 500500 days. At day 10011001 prices are [1001,1001][1001, 1001] so can't buy anymore. In total, you bought 5002+5001=1500500 \cdot 2 + 500 \cdot 1 = 1500 packs.