C. Save More Mice | Codeforces Round #748 (Div. 3)

C. Save More Mice

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

There are one cat, k$k$ mice, and one hole on a coordinate line. The cat is located at the point 0$0$, the hole is located at the point n$n$. All mice are located between the cat and the hole: the i$i$-th mouse is located at the point xi$x_i$ (0<xi<n$0<x_i<n$). At each point, many mice can be located.

In one second, the following happens. First, exactly one mouse moves to the right by 1$1$. If the mouse reaches the hole, it hides (i.e. the mouse will not any more move to any point and will not be eaten by the cat). Then (after that the mouse has finished its move) the cat moves to the right by 1$1$. If at the new cat's position, some mice are located, the cat eats them (they will not be able to move after that). The actions are performed until any mouse hasn't been hidden or isn't eaten.

In other words, the first move is made by a mouse. If the mouse has reached the hole, it's saved. Then the cat makes a move. The cat eats the mice located at the pointed the cat has reached (if the cat has reached the hole, it eats nobody).

Each second, you can select a mouse that will make a move. What is the maximum number of mice that can reach the hole without being eaten?

Input

The first line contains one integer t$t$ (1≤t≤104$1\le t\le {10}^4$) — the number of test cases. Then t$t$ test cases follow.

Each test case consists of two lines. The first line contains two integers n$n$ and k$k$ (2≤n≤109$2\le n\le {10}^9$, 1≤k≤4⋅105$1\le k\le 4\cdot {10}^5$). The second line contains k$k$ integers x1,x2,…xk$x_1,x_2,\dots x_k$ (1≤xi<n$1\le x_i<n$) — the initial coordinates of the mice.

It is guaranteed that the sum of all k$k$ given in the input doesn't exceed 4⋅105$4\cdot {10}^5$.

Output

For each test case output on a separate line an integer m$m$ (m≥0$m\ge 0$) — the maximum number of mice that can reach the hole without being eaten.

Example

input

Copy

3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11

output

Copy

3
1
4

The solution to the above problem is 

#include <bits/stdc++.h>

using namespace std;

#define int            long long int

#define F              first

#define S              second

#define pb             push_back

#define si             set <int>

#define vi             vector <int>

#define pii            pair <int, int>

#define vpi            vector <pii>

#define vpp            vector <pair<int, pii>>

#define mii            map <int, int>

#define mpi            map <pii, int>

#define spi            set <pii>

#define endl           "\n"

#define sz(x)          ((int) x.size())

#define all(p)         p.begin(), p.end()

#define double         long double

#define que_max        priority_queue <int>

#define que_min        priority_queue <int, vi, greater<int>>

#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

#define print(a)       for(auto x : a) cout << x << " "; cout << endl

#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl

#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)

{

    int x = 1;

    while (b)

    {

        if (b & 1) x *= a;

        a *= a;

        b >>= 1;

    }

    return x;

}

template <typename Arg1>

void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }

template <typename Arg1, typename... Args>

void __f (const char* names, Arg1&& arg1, Args&&... args)

{

    const char* comma = strchr (names + 1, ',');

    cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);

}

const int N = 200005;

void solve() {

    

    int n,k;

    cin>>n>>k;

    vi v(k);

    for(int i=0; i<k; i++){

        cin>>v[i];

    }

    sort(v.begin(),v.end());

    int ans=0,l=0,r=k-1;

    int curr=0,time=0;

    while(l<=r){

        ans++;

        curr=n-v[r];

        r--;

        time+=curr;

        while(l<=r && v[l]<=time){

            l++;

        }

    }

    cout<<ans<<endl;

    

}

int32_t main()

{

    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifndef ONLINE_JUDGE

    freopen("input.txt",  "r",  stdin);

    freopen("output.txt", "w", stdout);

#endif

    clock_t z = clock();

    int t = 1;

    cin >> t;

    while (t--) solve();

    cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);

    return 0;

}