fork download
//To debug :  g++ -g file.cpp -o code
//to flush output : fflush(stdout) or cout.flush()
//cout<<setprecision(p)<<fixed<<var
//use 1LL<<i to for 64 bit shifting , (ll)2 because by default 2 is ll
//take care of precedence rule of operators 
//do not forget to change the sizes of arrays and value of contants and other things after debugging  
 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,n) for(i=a;i<n;++i)
#define irep(i,n,a) for(i=n;i>a;--i)
#define mod 1000000007
#define pb push_back
#define big 9223372036854775807
#define big1 LONG_MAX
#define big2 ll_MAX
#define big3 1000000000
#define sma1 LONG_MIN
#define sma2 ll_MIN
#define sma3 -1000000000
#define mp make_pair
#define dub double
#define ivec vector<ll>
#define lvec vector<long long>
#define cvec vector<char>
#define svec vector<string>
#define mt make_tuple
#define MOD 998244353
#define ld long double
#define pi acos(-1.0)
 
#define SZ(x)  (ll)(x.size())
 
//comment the below if not required
 
/*
 
#define ss second.second
#define ff first.first
#define f first
#define s second
#define sf second.first
#define fs first.second
*/
 
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

//cout<<"Case #"<<c<<": "<<ans<<"\n" ;

int main()
{
    IOS;

    int t,C=0,n,i,j,pt,ft,r,c,cur,rt;
    ll tot,val,ans;


    cin>>t;

    while(t--)
    {
        ++C;
        cout<<"Case #"<<C<<": ";

        cin>>n;

        pair<int,int> p[n+1];

        tot = 0;
        r = 0;

        multiset<pair<int,int>> tft ; //fotget time (ft) and toy number

        rep(i,1,n+1)
        {
            cin>>pt>>ft;
            p[i]={pt,ft};
            tot += (ll)pt ; //total playing time
            tft.insert({-ft,i});
        }

        ans = tot;

        bool m[n+1]={0}; //to mark if toy has been removed

        rt = 0;
        val = 0;

        for(i=1;i<=n;++i)
        {


            if(!m[i])
            {
                //if this toy not removed , tot-pt

                if(p[i].second>(tot-(ll)p[i].first))
                {
                    //remove this toy and all other toys
                    //whose ft > tot-p[i].first-p[other toy playing time]

                    tot -= (ll)p[i].first;

                    vector<int> rem;

                    m[i]=1;
                    rem.pb(i);
                    ++rt;


                    for(auto u : tft)
                    {
                        int ind = u.second;

                        if(!m[ind])
                        {
                            int temp = -u.first;
                            m[ind]=1;

                            if(temp>(tot-(ll)p[ind].first))
                            {   
                                tot -= (ll)p[ind].first;

                                rem.pb(ind);
                                ++rt;
                                if(ind<i)
                                {
                                    val -= (ll)p[ind].first;
                                }
                            }
                            else
                                break;
                        }
                    }

                    for(auto ind : rem)
                    {
                        auto v = tft.find({-p[ind].second,ind});
                        tft.erase(v);
                    }


                }
                else
                {
                    val += (ll)p[i].first;

                    if((tot+val)>ans)
                    {
                        ans = tot + val;
                        r = rt;
                    }
                }


            }
            

        }


        if(SZ(tft))
                cout<<rt<<" "<<"INDEFINITELY\n";
        else
            cout<<r<<" "<<ans<<"\n";



    }



    return 0;
}
Success #stdin #stdout 0s 4348KB
stdin
4
1
5 1
2
5 10
10 3
3
30 17
5 10
10 3
3
5 10
5 10
5 11
stdout
Case #1: 0 5
Case #2: 0 INDEFINITELY
Case #3: 1 INDEFINITELY
Case #4: 0 25