codeforces#P1671C. Dolce Vita
Dolce Vita
Description
Turbulent times are coming, so you decided to buy sugar in advance. There are shops around that sell sugar: the -th shop sells one pack of sugar for 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 , during the second day cost is , during the third day — and so on for each shop .
On the contrary, your everyday budget is only coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding . 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 , 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 () — the number of test cases. Next cases follow.
The first line of each test case contains two integers and (; ) — the number of shops and your everyday budget.
The second line of each test case contains integers () — the initial cost of one pack in each shop.
It's guaranteed that the total sum of doesn't exceed .
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 () — the number of test cases. Next cases follow.
The first line of each test case contains two integers and (; ) — the number of shops and your everyday budget.
The second line of each test case contains integers () — the initial cost of one pack in each shop.
It's guaranteed that the total sum of doesn't exceed .
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
Note
In the first test case,
- Day 1: prices are . You can buy all packs, since .
- Day 2: prices are . You can't buy all packs, since , so you buy only packs.
- Day 3: prices are . You can buy packs with prices and .
- Day 4: prices are . You can't buy packs anymore, so you buy only pack.
- Day 5: prices are . You can buy pack.
- Day 6: prices are . You can buy pack.
- Day 7: prices are . You still can buy pack of cost .
- Day 8: prices are . Prices are too high, so you can't buy anything.
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 packs first days. At day prices are , so you can buy only pack the next days. At day prices are so can't buy anymore. In total, you bought packs.