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 aiai 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 aiai, during the second day cost is ai+1ai+1, during the third day — ai+2ai+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?
Input
The first line contains a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases. Next tt cases follow.
The first line of each test case contains two integers nn and xx (1≤n≤2⋅1051≤n≤2⋅105; 1≤x≤1091≤x≤109) — the number of shops and your everyday budget.
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the initial cost of one pack in each shop.
It's guaranteed that the total sum of nn doesn't exceed 2⋅1052⋅105.
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.
Example
input
Copy
4 3 7 2 1 2 5 9 10 20 30 40 50 1 1 1 2 1000 1 1
output
Copy
11 0 1 1500
Note
In the first test case,
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 500⋅2+500⋅1=1500500⋅2+500⋅1=1500 packs.
思路：贪心的来想，我们要买到多点的糖肯定买最便宜的，先排序，然后我们想算最大能买到哪，肯定需要算前缀和。
我们一个一个算肯定会超时，那么我们就设第i包最大能最多买ki天，然后我们列出柿子：(a1+ki-1)+(a2+ki-1)+...+(ai+ki-1)<=x，化简得ki=(x-si)/i+1,算出每个的最大天数，刚好等于她最多能买多少包，因为在算第n个的时候我们必须要把之前的包数算上之后得出来的最大天数，越往后的天数里能买的包数在减少，假设第一天能买第k包，那么到最后就只能买第1包，那么我们算的最大天数刚好就是每包能买的最大包数，自己模拟一下理解一下。
- #include<iostream>
- #include<algorithm>
- #include<cstring>
-
- using namespace std;
- int n,x;
- const int N=200005;
- typedef long long ll;
- ll a[N];
- ll s[N];
- void sove(){
- cin>>n>>x;
- for(int i=1;i<=n;i++){
- cin>>a[i];
- }
- sort(a+1,a+1+n);
- for(int i=1;i<=n;i++){
- s[i]=s[i-1]+a[i];
- }
- ll con=0;
- for(int i=1;i<=n;i++){
- if(x-s[i]>=0){
- con+=(x-s[i])/i+1;
- }
- }
- cout<<con<<endl;
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie() ,cout.tie() ;
- int t;
- cin>>t;
- while(t--){
- sove();
- }
- return 0;
- }