#include<iostream>
#include<algorithm>
using namespace std;
int W,c;
const int N=1e5+5;
struct Tree {
	int w,d;
} t[N];
int wight[N],branch[N];
int tot,hd[N],nxt[N<<1],to[N<<1];
void addedge(int u,int v) {
	++tot,to[tot]=v,nxt[tot]=hd[u],hd[u]=tot;
}
void input(int x,int d) {
	int g=0;
	while(g<d) {
		++g,++c;
		scanf("%d%d",&t[c].w,&t[c].d);
		addedge(x,c);
		input(c,t[c].d);
	}
}
int dfs(int x) {
	int sum=0,top=0;
	for(int i=hd[x]; i; i=nxt[i]) {
		int goal=to[i];
		sum+=dfs(goal);
	}
	wight[1]=0;
	for(int i=hd[x]; i; i=nxt[i])
		if(t[to[i]].w)wight[++top]=t[to[i]].w;
	sort(wight+1,wight+1+top);
	int L=2,R=top,g=1;
	branch[1]=wight[1];
	while(L<=R) {
		branch[++g]=wight[R--];
		while(L<=R&&branch[g]+wight[L]<=W)branch[g]+=wight[L],L++;
	}
//	printf(" w=%d d=%d g=%d\n",t[x].w,t[x].d,g);
	if(t[x].d) {
		if(g==1) {
			t[x].w+=branch[1];
			sum=sum+t[x].w/W,t[x].w%=W;
		} else if(g==2) {
			if(branch[1]+branch[2]<=W) {
				t[x].w+=branch[1]+branch[2];
				sum=sum+t[x].w/W,t[x].w%=W;
//				printf("  [1] sum=%lld x=%d %d\n",sum,x,t[x].w);
			} else {
				t[x].w+=branch[1];
				sum=sum+t[x].w/W+1,t[x].w%=W;
//				printf("  [2] sum=%lld x=%d %d\n",sum,x,t[x].w);
			}
		} else {
			sort(branch+2,branch+1+g);
			if(branch[1]+branch[3]<=W) {
				t[x].w+=branch[2];
				sum=sum+t[x].w/W+g-2,t[x].w%=W;
			} else if(branch[1]+branch[2]<=W) {
				t[x].w+=branch[1]+branch[2];
				sum=sum+t[x].w/W+g-2,t[x].w%=W;
			} else {
				t[x].w+=branch[1];
				sum=sum+t[x].w/W+g-1,t[x].w%=W;
			}
		}
	} else {
		sum=sum+t[x].w/W,t[x].w%=W;
	}
	printf("sum=%lld x=%d %d\n",sum,x,t[x].w);
	return sum;
}
int main() {
	scanf("%d",&W);
	++c;
	scanf("%d%d",&t[c].w,&t[c].d);
	input(1,t[1].d);
	printf("%d\n",dfs(1)+(t[1].w!=0));
	return 0;
}