#define 草 包裹。

考虑暴力怎么做，贪心显然能做，但是没啥优化空间，考虑 DP。

显然奶牛不会在没有东西的地方掉头，考虑把奶牛和草的坐标排序，然后按照坐标顺序 DP。

将相邻的位置之间视为一个段，容易发现每个段只会被经过 $0,1,2$ 次，令 $d_i$ 表示第 $i$ 段经过的次数，将问题转化为求一个符合条件的 $d$ 使其加权和最小。

考虑分析 $d$ 的充要条件，充要条件如下：

• 草旁边至少有一个位置非 $0$。
• 如果这个位置有一头牛，则两侧不能为 $11$ 或 $22$。
• 如果这个位置有两头及以上牛，则不做任何限制。
• 所有非 $0$ 段至少连接一头牛。

令 $f_{i,1/2/3/4/5}$ 表示第 $i$ 个位置，不考虑第 $i$ 个位置是啥（这个限定是为了方便后面矩阵的边界处理），如下状态的答案。

1. 上一段是 $1$，未连接牛。
2. 上一段是 $2$，未连接牛。
3. 上一段是 $1$，已连接牛。
4. 上一段是 $2$，已连接牛。
5. 上一段是 $0$。

转移显然。

考虑使用 $(\min,+)$ 矩阵维护 DP，注意到 $M$ 是给定的，考虑将数轴划分为若干周期，即 $[0,M),[M,2M),[2M,3M)\dots$，当加入 $(l,r)$ 时，相当于修改了 $l,r$ 中间的周期。

套路地扫描线，使用线段树维护一个周期的信息，具体地，将操作坐标离散化，线段树维护 $[0,M)$ 中所有操作涉及到的坐标，每个节点 $[x,y]$ 维护第 $x$ 个坐标转移到第 $y$ 个坐标的矩阵，以及最右侧坐标是一头牛还是两头牛还是草，并插入 $0,M$ 为哨兵节点。还需要维护全 $0$ 前缀长度和全 $0$ 后缀长度来合并区间。

合并区间大概是算出中间长度 $dis$，通过左侧区间最后一个非空坐标的状态（草/一头牛/两头牛）构造出中间转移一步的矩阵，之后将左侧矩阵、中间矩阵、右侧矩阵乘起来合并。

扫描线时，假设本次操作坐标为 $x$，上一次操作坐标为 $y$，则当 $\lfloor\frac{x}{m}\rfloor\neq \lfloor\frac{y}{m}\rfloor$ 时，操作中间跨过了不少于 $1$ 个周期，应该统计答案，从线段树根节点查询这个周期的转移矩阵，把答案乘上转移矩阵的 $\lfloor\frac{x}{m}\rfloor-\lfloor\frac{y}{m}\rfloor$ 次方。

更新答案的过程和线段树合并区间的过程是一样的，可以将答案初值设成 $(\min,+)$ 单位矩阵，此时最后一行与 DP 初值恰好吻合，因此最后直接使用答案矩阵的最后一行作为 DP 数组即可，注意需要特判最后位置是牛还是草，因为我们 DP 时没有考虑最后一位。

/*
f_{i,1/2/3/4/5}（不考虑放在 i 的东西） 
1:1，未连接 
2:2，未连接 
3:1，已连接 
4:2，已连接
5:0 

i-1 grass
f[i][1]=f[i-1][1/5]+dis
f[i][2]=f[i-1][2/5]+2*dis
f[i][3]=f[i-1][3]+dis
f[i][4]=f[i-1][4]+2*dis
f[i][5]=f[i-1][3/4]
i-1 1cow
f[i][1]=nothing
f[i][2]=nothing
f[i][3]=f[i-1][2/4/5]+dis
f[i][4]=f[i-1][1/3/5]+2*dis
f[i][5]=f[i-1][1/2/3/4/5]
i-1 2cow
f[i][1]=nothing
f[i][2]=nothing
f[i][3]=f[i-1][1~5]+dis
f[i][4]=f[i-1][1~5]+2*dis
f[i][5]=f[i-1][1~5]
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define GRASS 0
#define COW1 1
#define COW2 2
const int inf=0x3f3f3f3f3f3f3f3f;
struct Matrix{
	int n,m,a[6][6];
	Matrix(){
		memset(a,0x3f,sizeof(a));
	}
	Matrix(int _n,int _m){
		n=_n,m=_m;
		memset(a,0x3f,sizeof(a));
	}
	Matrix operator * (Matrix b) {
		assert(m==b.n);
		Matrix c(n,b.m);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(a[i][j]>inf/2) continue; 
				for(int k=1;k<=b.m;k++){
					if(b.a[j][k]>inf/2) continue;
					c.a[i][k]=min(c.a[i][k],a[i][j]+b.a[j][k]);
				}
			}
		}
		return c;
	}
	void init(int op,int dis){
		//f_i ->(dis)-> f_{i+1} 
		memset(a,0x3f,sizeof(a));
		n=m=5;
		if(op==GRASS){
			/*
			1----
			-2---
			--1-0
			---20
			12---
			*/
			a[1][1]=a[5][1]=dis;
			a[2][2]=a[5][2]=2*dis;
			a[3][3]=dis;
			a[4][4]=2*dis;
			a[3][5]=a[4][5]=0;
		}else if(op==COW1){
			/*
			---20
			--1-0
			---20
			--1-0
			--120
			*/
			a[2][3]=a[4][3]=a[5][3]=dis;
			a[1][4]=a[3][4]=a[5][4]=2*dis;
			a[1][5]=a[2][5]=a[3][5]=a[4][5]=a[5][5]=0;
		}else if(op==COW2){
			/*
			--120
			--120
			--120
			--120
			--120
			*/
			a[1][3]=a[2][3]=a[3][3]=a[4][3]=a[5][3]=dis;
			a[1][4]=a[2][4]=a[3][4]=a[4][4]=a[5][4]=2*dis;
			a[1][5]=a[2][5]=a[3][5]=a[4][5]=a[5][5]=0;
		}
	}
};
int m,n,P;
int b[200005],tot;
struct opt{
	int pos,addcow,addgrass;
	bool operator<(const opt &b) const{
		return pos<b.pos;
	}
};
vector<opt> V;
struct data{
	int c,g;
	int pre,suf;//前缀0段，后缀0段 
	int op;
	Matrix v;// 不含 pre 和 suf 的矩阵积 
	data merge(data x,data y);
};
data merge(data x,data y){
	if(x.c==0&&x.g==0&&y.c==0&&y.g==0){
		Matrix tmp(5,5);
		tmp.a[1][1]=tmp.a[2][2]=tmp.a[3][3]=tmp.a[4][4]=tmp.a[5][5]=0;
		return (data){0,0,0,x.suf+y.suf,0,tmp};
	}
	if(x.c==0&&x.g==0){
		y.pre+=x.suf;
		return y;
	}
	if(y.c==0&&y.g==0){
		x.suf+=y.suf;
		return x;
	}
	Matrix tmp(5,5);
	tmp.init(x.op,x.suf+y.pre);
	return {x.c+y.c,x.g+y.g,x.pre,y.suf,y.op,x.v*tmp*y.v};
}
data ksm(data A,int b) {
	data I;
	I.v.n=I.v.m=5;
	I.c=I.g=I.pre=I.suf=I.op=0;
	memset(I.v.a,0x3f,sizeof(I.v.a));
	for(int i=1;i<=5;i++) I.v.a[i][i]=0;
	while(b){
		if(b&1) I=merge(I,A);
		A=merge(A,A);
		b/=2;
	}
	return I;
}
struct SGT{
	struct sgtnode{
		int l,r;
		data x;
	}t[200005];
	void pushup(int p){
		t[p].x=merge(t[p*2].x,t[p*2+1].x);
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		if(l==r){
			t[p].x.v.n=t[p].x.v.m=5;
			for(int i=1;i<=5;i++) for(int j=1;j<=5;j++){
				if(i==j) t[p].x.v.a[i][j]=0;
				else t[p].x.v.a[i][j]=inf;
			}
			t[p].x.pre=0,t[p].x.suf=b[l+1]-b[l];
			return;
		}
		int mid=(l+r)/2;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		pushup(p);
	}
	void modify(int p,int pos,int c,int g){
		if(t[p].l==t[p].r){
			t[p].x.c+=c,t[p].x.g+=g;
			if(t[p].x.c>=2){
				t[p].x.op=COW2;
			}else if(t[p].x.c>=1){
				t[p].x.op=COW1;
			}else{
				t[p].x.op=GRASS;
			}
			return;
		}
		int mid=(t[p].l+t[p].r)/2;
		if(mid>=pos) modify(p*2,pos,c,g);
		else modify(p*2+1,pos,c,g);
		pushup(p);
	} 
}sgt;
data ans;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n>>P;
	for(int i=1;i<=n;i++){
		int l,r;
		cin>>l>>r;
		V.push_back({l,1,0});
		V.push_back({r+m,-1,0});
		b[++tot]=l%m;
	}
	for(int i=1;i<=P;i++){
		int l,r;
		cin>>l>>r;
		V.push_back({l,0,1});
		V.push_back({r+m,0,-1});
		b[++tot]=l%m;
	}
	b[++tot]=0,b[++tot]=m;
	sort(V.begin(),V.end());
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	sgt.build(1,1,tot-1);
	int lst=-1;
	memset(ans.v.a,0x3f,sizeof(ans.v.a));
	ans.v.n=5,ans.v.m=5;
	ans.v.a[1][1]=ans.v.a[2][2]=ans.v.a[3][3]=ans.v.a[4][4]=ans.v.a[5][5]=0;
	for(auto tmp:V){
		int p=tmp.pos,c=tmp.addcow,g=tmp.addgrass;
		if(lst!=-1&&p/m!=lst){
			ans=merge(ans,ksm(sgt.t[1].x,p/m-lst));
		}
		lst=p/m;
		sgt.modify(1,lower_bound(b+1,b+1+tot,p%m)-b,c,g);
	}
	if(ans.op==GRASS){
		cout<<min(ans.v.a[5][3],ans.v.a[5][4])<<"\n";
	}else{
		int res=inf;
		for(int i=1;i<=5;i++) res=min(res,ans.v.a[5][i]);
		cout<<res<<"\n";
	}
}