//本来打算做dvi2前三题,但是c题直接1800,果断放弃（才怪）

A

//A就不上了，就是调的时候有点烦

B

//无需多言，就是贪心的。首先数组有一个公共的最小缺数。
//那么划分后必须公共缺失数是他，证明：1不可能有大的
//拆分后若存在缺小的，那么这个小的一定会存在其他某个子段，不///符合
//其次贪心的构造字段，为了减少计算和分段会导致数越来越稀薄，
//那么假设这个数组可以成功拆分，那么第一组恰好满足小于公共
//值全部出现，然后检验第二组就可以
//题解竟然是前后缀
//要关机了，明天再看
#include <bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    map<int,int> ma;
    vector<int> vc(n);
    int mmax=0;
    for(int i=0;i<n;i++){
        cin>>vc[i];
        mmax=max(vc[i],mmax);
        ma[vc[i]]++;
    }
    int index=0;
    for(int i=0;i<=n;i++){
        if(ma.find(i)==ma.end()){
            index=i;
            break;
        }
    }
        int cnt=0;
        int i=0;
        int edge=0;
        for(int j=0;j<2;j++){
        unordered_map<int,int> mp;
        for(i;i<n;i++){
            if(vc[i]<index){mp[vc[i]]++;}
            if((int)mp.size()==index){
                if(cnt==1){
                    cnt++;
                    break;
                }
                cnt++;
                edge=i+1;
                i++;
                break;
            }
        }

        }
        if(cnt==2)
        cout<<2<<"\n"<<1<<" "<<edge<<"\n"<<edge+1<<" "<<n<<"\n";
        else cout<<"-1\n";


}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

C

//以为自己可以de出1800的dp，但是总是差一些，对比标准答案
//更理解dp是一种求解的工具，甚至可以”剪枝“，有很多优化的方法
// 首先对数组按照b升序排序,保证选择k组后公式可以化简为sum(a)+b[k]-b[1];
// 那么设计状态转移方程,f n n表示前n个组,k表示取出来的组数,n表示三
//那么任1组可以当头，也就是j等于1的时候，
//其他的时候只需要if(f[i-1][j-1]+bian[i].a+bian[i].b<=l)
//更新答案————————记住，dp不一定要设计的和所求一致，可以间接求
//标准答案是二分，明天再看。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
  ll a,b;
};
void solve(){
    ll n,l;
    cin>>n>>l;
    vector<edge> bian(n+1);
    for(int i=1;i<=n;i++){
        cin>>bian[i].a>>bian[i].b;
    }
    //排序
    sort(bian.begin()+1,bian.end(),[](edge A,edge B){
        if(A.b==B.b){
            return A.a<B.a;
        }
        return A.b<B.b;
    });
    vector<vector<ll>> f(n+1, vector<ll>(n+1,ll(1e17)));

    ll ans=0;
    f[0][0]=0;

    for(int i=1;i<=n;i++){
        if(bian[i].a<=l) ans=max(ans,(ll)1);
        for(int j=1;j<=i;j++){
            if(j==1){
                 f[i][1]=min(f[i-1][1],bian[i].a-bian[i].b);
            }
            else{
            if(f[i-1][j-1]+bian[i].a+bian[i].b<=l) ans=max(ans,(ll)j);
            f[i][j]=min(f[i-1][j-1]+bian[i].a,f[i-1][j]);
            }
        }
    }

    cout<<ans<<"\n";
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}
//原本的繁杂思路，还有一些缺陷

// 首先对数组按照b升序排序,保证选择k组后公式可以化简为sum(a)+b[k]-b[1];
// 那么设计状态转移方程,f n k 3,n表示前n个组,k表示取出来的组数,n表示三种状态,分别 
//1表示此时选已经选了第一个加b了
//0表示没有选,选的话加a[i]
//2表示选好了末尾,就是a[i]+b[i]
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct edge{
  ll a,b;
};
void solve(){
    ll n,l;
    cin>>n>>l;
    vector<edge> bian(n+1);
    for(int i=1;i<=n;i++){
        cin>>bian[i].a>>bian[i].b;
    }
    //排序
    sort(bian.begin()+1,bian.end(),[](edge A,edge B){
        if(A.b==B.b){
            return A.a<B.a;
        }
        return A.b<B.b;
    });
    ll k=n;
    vector<vector<vector<ll>>> f(n+1, vector<vector<ll>>(k+1, vector<ll>(3, ll(1e17))));
    ll ans=0;
    f[1][1][2]=bian[1].a;
    f[1][1][1]=bian[1].a-bian[1].b;
    //  for(int i=1;i<=n;i++){
    //     cout<<bian[i].a<<" "<<bian[i].b<<"\n";
    // }


    f[1][1][0]=bian[1].a;
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){

                                 //选           
            f[i][j][0]=min(f[i-1][j-1][0]+bian[i].a,f[i-1][j][0]);
                //不选                   

                            //不选          //选
            f[i][j][1]=min(f[i-1][j][1],f[i-1][j-1][0]+bian[i].a-bian[i].b);


            if(j==1){
                f[i][j][2]=min(f[i-1][j][2],bian[i].a);
            }else{
                             //选                                    //不选
                f[i][j][2]=min(f[i-1][j-1][1]+bian[i].a+bian[i].b,f[i-1][j][2]);
                                //选最后一个最为结束点        //继承
            }

          // cout<<f[i][j][0]<<"   "<<f[i][j][1]<<"   "<<f[i][j][2]<<"   "<<j<<"\n";

        }
    }
    for(ll i=k;i>=1;i--){
        if(f[n][i][2]<=l){
            ans=i;
            break;
        }
    }
    cout<<ans<<"\n";
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}