#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 2000

enum Type{
	MATH,
	IT,
};

struct Info{

	Info(){
		start = end = 0;
		type = MATH;
		finished = false;
		index = 0;
	}
	Info(int arg_start,int arg_end,Type arg_type,bool arg_finished,int arg_index){
		start = arg_start;
		end = arg_end;
		type = arg_type;
		finished = arg_finished;
		index = arg_index;
	}

	bool operator<(const struct Info &arg) const{
		return end < arg.end;
	}

	int start,end,index;
	Type type;
	bool finished;
};

//辺を表す構造体(行先、容量、逆辺のインデックス)
struct Edge{
	Edge(int arg_to,int arg_capacity,int arg_rev_index){
		to = arg_to;
		capacity = arg_capacity;
		rev_index = arg_rev_index;
	}
	int to,capacity,rev_index;
};

int N,M;

int dist[NUM]; //sourceからの距離
int cheked_index[NUM]; //どこまで調べ終わったか
int index_table[405][2],work_index[405][2];
int V,E;
vector<Info> info;
vector<Edge> G[NUM]; //グラフの隣接リスト表現


//fromからtoへ向かう容量capacityの辺をグラフに追加する
void add_edge(int from,int to,int capacity){
	G[from].push_back(Edge(to,capacity,G[to].size()));
	G[to].push_back(Edge(from,0,G[from].size()-1)); //逆辺の、初期容量は0
}

//sourceからの最短距離をBFSで計算する
void bfs(int source){
	for(int i = 0; i < V; i++)dist[i] = -1;
	queue<int> Q;
	dist[source] = 0;
	Q.push(source);

	while(!Q.empty()){
		int node_id = Q.front();
		Q.pop();
		for(int i = 0; i < G[node_id].size(); i++){
			Edge &e = G[node_id][i];
			if(e.capacity > 0 && dist[e.to] < 0){ //辺の容量が正で、かつエッジの行先に未訪問の場合
				dist[e.to] = dist[node_id]+1;
				Q.push(e.to);
			}
		}
	}
}

//増加パスをDFSで探す
int dfs(int node_id,int sink,int flow){
	if(node_id == sink)return flow; //終点についたらflowをreturn

	for(int &i = cheked_index[node_id]; i < G[node_id].size(); i++){ //node_idから出ているエッジを調査
		Edge &e = G[node_id][i];
		if(e.capacity > 0 && dist[node_id] < dist[e.to]){ //流せる余裕があり、かつsourceからの距離が増加する方法である場合
			int tmp_flow = dfs(e.to,sink,min(flow,e.capacity)); //流せるだけ流す
			if(tmp_flow > 0){ //流せた場合
				e.capacity -= tmp_flow; //流した分、エッジの容量を削減する
				G[e.to][e.rev_index].capacity += tmp_flow; //逆辺の容量を、流した分だけ増加させる
				return tmp_flow;
			}
		}
	}
	return 0;
}


//sourceからsinkへの最大流を求める
int max_flow(int source,int sink){ //source:始点 sink:終点
	int flow = 0,add;
	while(true){ //増加パスが存在する限り、流量を追加し続ける
		bfs(source);
		if(dist[sink] < 0)break; //sourceからsinkへと辿り着く残余グラフがない、つまり増加パスが無くなった場合、break
		for(int i = 0; i < V; i++)cheked_index[i] = 0;
		while((add = dfs(source,sink,BIG_NUM)) > 0){ //増加パスが見つかる間、加算
			flow += add;
		}
	}
	return flow;
}


int main(){

	scanf("%d %d",&N,&M);

	int start,end;
	Type type;

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

		scanf("%d %d",&start,&end);

		if(i < M){

			type = MATH;

		}else{

			type = IT;
		}
		info.push_back(Info(start,end,type,false,i));
	}

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

	int maximum = 0;
	int min_end,min_index,loc;

	//最大値を貪欲法で調べる
	for(int day = 1; day <= 400; day++){
		//一番早く締め切りが来る日を調べる.複数あれば、IDが最小のもの
		min_end = BIG_NUM;
		min_index = BIG_NUM;

		for(int i = 0; i < info.size(); i++){
			if(info[i].finished == false && info[i].start <= day && info[i].end >= day && min_end > info[i].end){

				min_end = info[i].end;
				min_index = info[i].index;
				loc = i;

			}else if(info[i].finished == false && info[i].start <= day && info[i].end >= day && min_end == info[i].end
					&& min_index > info[i].index){
				min_index = info[i].index;
				loc = i;
			}
		}
		if(min_end == BIG_NUM)continue; //今日やれる宿題はない

		info[loc].finished = true;

		maximum++;
	}

	printf("%d\n",maximum);

	//最大流で、最小値を求める→数学と情報両方選べる日のみに流れる。他の片方しかやれない日は、もう一方をコインで引けば良いということ
	int source = 0,sink = 1,index = 2;

	//日付ノード:情報
	for(int i = 1; i <= 400; i++){

		index_table[i][IT] = index++;
	}

	//日付ノード:数学
	for(int i = 1; i <= 400; i++){

		index_table[i][MATH] = index++;
		add_edge(index_table[i][IT],index_table[i][MATH],1); //情報→数学に辺を張る
	}

	int count_it = 0,count_math = 0;

	//情報の宿題に辺を張る
	for(int i = 0; i < info.size(); i++){
		if(info[i].type == MATH)continue;

		work_index[count_it][IT] = index++;
		add_edge(source,work_index[count_it][IT],1); //スタートから情報の宿題に辺を張る
		for(int k = info[i].start; k <= info[i].end; k++){ //宿題から日付に辺を張る

			add_edge(work_index[count_it][IT],index_table[k][IT],1);
		}
		count_it++;
	}

	//数学の宿題
	for(int i = 0; i < info.size(); i++){
		if(info[i].type == IT)continue;

		work_index[count_math][MATH] = index++;
		add_edge(work_index[count_math][MATH],sink,1); //sinkへ辺を張る

		for(int k = info[i].start; k <= info[i].end; k++){

			add_edge(index_table[k][MATH],work_index[count_math][MATH],1); //数学の日から数学の宿題に辺を張る
		}
		count_math++;
	}

	V = index;
	printf("%d\n",max_flow(source,sink));

	return 0;
}



Measured memory_bytes: 4808