#include<bits/stdc++.h>
#define loop(a,b,c,d) for(int a=b; a<c; a+=d)
#define loop2(a,b,c,d) for(int a=b; a>=c; a-=d)
#define bl(i,n) loop(i,0,n,1)
#define bl2(i,n) loop2(i,n,0,1)
#define int long long
#define nl endl
#define g ' '
using namespace std;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);cout.tie(NULL);
int n, m, h;
cin>>n>>m>>h;
vector<pair<int,int> > flights[n];
bl(i,n-1){
bl(_,h){
int a, b;
cin>>a>>b;
if(a <= i) continue;
flights[a].push_back(make_pair(i, b));
}
}
int last = 0;
vector<vector<int> > dp(n, vector<int>(m, 0));
dp[0][0] = 1;
for(int i=1; i<n; i++){
for(int j=0; j<m; j++){
if(j >= 1) dp[i][j] = dp[i][j-1];
for(auto from : flights[i]){
if(dp[i][j] >= 500000001){
dp[i][j] = 500000001;
break;
}
if(j >= from.second) dp[i][j] += dp[from.first][j - from.second];
}
if(dp[i][j] >= 500000001){
dp[i][j] = 500000001;
}
if(i == n-1) cout<<dp[i][j]<<g;
}
}
return 0;
}
