#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<int,int>a[1010],b[1010],aa[1010],bb[1010];
int f[440][440][440];
int used[1010];
int n1,n2;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    int m1=m,m2=n-m;
    for (int i=1;i<=m1;i++)
    cin>>a[i].first>>a[i].second;
    // sort(a+1,a+m1+1);
    {
        memset(used,0,sizeof(used));
        for (int i=1;i<=400;i++){
            int mn=1e9,xu=0;
            for (int j=1;j<=m1;j++)
            if(used[j]==0&&a[j].first<=i&&a[j].second>=i)
            if(mn>a[j].second)mn=a[j].second,xu=j;
            if(xu!=0)used[xu]=1,aa[++n1]=a[xu];
        }

    }
    // for (int i=1;i<=n1;i++)
    // cout<<aa[i].first<<"~~~"<<aa[i].second<<"\n";
    for (int i=1;i<=m2;i++)
    cin>>b[i].first>>b[i].second;
    // sort(b+1,b+m2+1);
    {
        memset(used,0,sizeof(used));
        for (int i=1;i<=400;i++){
            int mn=1e9,xu=0;
            for (int j=1;j<=m2;j++)
            if(used[j]==0&&b[j].first<=i&&b[j].second>=i)
            if(mn>b[j].second)mn=b[j].second,xu=j;
            if(xu!=0)used[xu]=1,bb[++n2]=b[xu];
        }
    }
    // for (int i=1;i<=n2;i++)
    // cout<<bb[i].first<<"~~~"<<bb[i].second<<"\n";
    memset(f,63,sizeof(f));
    f[0][0][0]=0;
    swap(m1,n1);swap(m2,n2);
    // cout<<m1<<"!!!"<<m2<<"\n";

    for (int i=1;i<=400;i++){
        
        for (int j=1;j<=m1;j++)if(aa[j].first<=i&&aa[j].second>=i){
            int mn=1e9;
            for (int jj=j+1;jj<=m1;jj++)
            if(aa[jj].first<=i&&aa[jj].second>=i)mn=min(mn,aa[jj].second);
            if(mn<aa[j].second)continue;
            for (int jj=j-1;jj>=0;jj--){
                for (int k=0;k<=m2;k++)
                f[i][j][k]=min(f[i-1][jj][k]+1,f[i][j][k]);
                if(jj!=j&&aa[jj].first<=i&&aa[jj].second>=i)break;
            }
        }
        for (int k=1;k<=m2;k++)if(bb[k].first<=i&&bb[k].second>=i){
            int mn=1e9;
            for (int kk=k+1;kk<=m2;kk++)
            if(bb[kk].first<=i&&bb[kk].second>=i)mn=min(mn,bb[kk].second);
            if(mn<bb[k].second)continue;
            for (int kk=k-1;kk>=0;kk--){
                for (int j=0;j<=m1;j++)
                f[i][j][k]=min(f[i-1][j][kk]+1,f[i][j][k]);
                if(kk!=k&&bb[kk].first<=i&&bb[kk].second>=i)break;
            }
        }
        for (int j=0;j<=m1;j++)
        for (int k=0;k<=m2;k++){
            int jj=j+1;
            while(jj<=m1&&aa[jj].second<i)jj++;
            int kk=k+1;
            while(kk<=m2&&bb[kk].second<i)kk++;
            if ((jj>m1||aa[jj].first>i)||(kk>m2||bb[kk].first>i))
            f[i][j][k]=min(f[i][j][k],f[i-1][j][k]);
        }    
        // for (int j=0;j<=m1;j++)
        // for (int k=0;k<=m2;k++)
        // cout<<i<<"!!"<<j<<" "<<k<<" "<<f[i][j][k]<<"\n";
        // for (int j=0;j<=m1;j++)
        // for (int k=0;k<=m2;k++)
        // f[i][j+1][k]=min(f[i][j+1][k],f[i][j][k]),
        // f[i][j][k+1]=min(f[i][j][k+1],f[i][j][k]);
    }
    int ans=f[401][0][0];
    for (int j=0;j<=m1;j++)
    for (int k=0;k<=m2;k++)
    // if(j==m1||k==m2)
    ans=min(ans,f[400][j][k]);

    swap(n1,m1);swap(n2,m2);
    for (int i=1;i<=m2;i++)
    a[++m1]=b[i];
    int ans2=0;
    memset(used,0,sizeof(used));
    for (int i=1;i<=400;i++){
        int mn=1e9,xu=0;
        for (int j=1;j<=m1;j++)
        if(used[j]==0&&a[j].first<=i&&a[j].second>=i)
        if(mn>a[j].second)mn=a[j].second,xu=j;
        if(xu!=0)used[xu]=1,ans2++;
    }
// cout<<m1<<"!!!!"<<m2<<"\n";
    cout<<ans2<<"\n"<<ans<<"\n";
}