#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,m,k,ls;
int c[200000],f[200000],ds[8],chk[200000][8],sur[200000],nb[8];
void dfs(int x){
	if(x==6){
		int ans=0;
		for(int i=1;i<=5;++i){
			if(ds[i]==1){
				for(int j=1;j<=nb[i];++j){
					sur[chk[j][i]]=1;
				}
			}
		}
		for(int i=1;i<=n;++i) if(sur[i]==0) ++ans;
		if(ans<=m) ls=max(ls,ans);
		for(int i=1;i<=5;++i){
			if(ds[i]==1){
				for(int j=1;j<=nb[i];++j){
					sur[chk[j][i]]=0;
				}
			}
		}
		return;
	}
	ds[x]=0;dfs(x+1);ds[x]=1;dfs(x+1);
	return;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;++i){
		scanf("%d%d",&c[i],&f[i]);
		chk[++nb[f[i]]][f[i]]=c[i];
	}
	dfs(1);printf("%d\n",ls);
	return 0;
}