Untitled

#include <bits/stdc++.h>

using namespace std;

vector<pair<int,int> > v;
vector<int> v1;
int c, nrProf, nrSali, x, y, cnt, nr_sali_libere, a=-1, b=-1, maxim, ans;
bool cmp(pair<int,int> x, pair<int,int> y){
    return (x.second<y.second) || (x.second==y.second && x.first>y.first);
}
bool cmp1(pair<int, int> x, pair<int, int> y){
    return (x.first<y.first) || (x.first==y.first && x.second<y.second);
}

bool verif(int val){
    for(int i=0; i<v.size(); i++){
        v[i].second=val+v[i].first;
    }
    for(int i=0; i<nrSali; i++){
        b=v[i].second;
        for(int j=i+nrSali; j<nrProf; j+=nrSali){
            if(b>v[j].first){
                return false;
            }
            b=v[j].second;
        }
    }
    return true;
}

void bs(int st, int dr){
    int mij=(st+dr)/2;
    if(st>=dr){
        return;
    }
    if(verif(mij)==true){
        ans=mij;
        bs(mij+1, dr);
    }
    else{
        bs(st, mij-1);
    }
}



int main()
{
    ifstream fin("cursuri.in");
    ofstream fout("cursuri.out");
    fin>>c;
    fin>>nrProf>>nrSali;
    nr_sali_libere=nrSali;
    for(int i=0; i<nrProf; i++){
        fin>>x>>y;
        v.push_back({x, y});
    }
    if(c==1){
        sort(v.begin(), v.end(), cmp);
        // for(int i=0; i<v.size(); i++){
        //     fout<<v[i].first<<" "<<v[i].second<<endl;
        // }
        for(int i=0; i<min(nrProf, nrSali); i++){
            v1.push_back(v[i].second);
        }
        cnt=nrSali;
        for(int i=nrSali; i<nrProf; i++){
            for(int j=0; j<nrSali; j++){
                if(v1[j]<=v[i].first){
                    v1[j]=v[i].second;
                    cnt++;
                }
            }
        }
        fout<<cnt;
    }
    else if(c==2){
        sort(v.begin(), v.end(), cmp1);
        for(int i=0; i<v.size(); i++){
            if(v[i].second-v[i].first>maxim){
                maxim=v[i].second-v[i].first;
            }
        }
        bs(1, maxim);
        fout<<ans;
    }

    return 0;
}