学步园

/*
 * 2159.cpp
 *
 *  Created on: 2013年7月29日
 *      Author: Administrator
 */

#include <iostream>


using namespace std;

int dp[105][105];
int n,m,K,s,w[105],r[105],e[105];

int main(){

	int i , j , k , l;

	while(cin>>n>>m>>K>>s){

		memset(dp,0,sizeof(dp));

		for(i=1;i<=K;++i){
			cin>>e[i]>>r[i];
		}


		for(j=1;j<=s;++j){//s:怪的个数
			for(k=1;k<=K;++k){//K:怪的种类数
				/**
				 * m:所剩的忍耐度
				 * r[k]:杀掉第k种怪的所掉的忍耐度
				 * e[k]:杀掉第k种怪的所获得的的经验值
				 *
				 *
				 */
				for(i=m;i>=r[k];--i){
					dp[i][j] = max(dp[i][j],dp[i-r[k]][j-1] + e[k]);
				}
			}
		}

		/**
		 * 以下循环判断到底要掉忍耐值才可以获得所需的经验值
		 */
		for( i = 0 ; i <= m ; ++i ){
			//dp[i][j]:忍耐度为i，还可以杀j个怪的时候所能获得的最大的经验值
			if(dp[i][s] >= n){
				break;
			}
		}

		int ans;


		if(i>m){//如果所需的忍耐度>所剩的忍耐度
			ans = -1;
		}else{
			//m-i。所剩的忍耐度-所需的忍耐度
			ans = m - i;
		}

		cout<<ans<<endl;
	}


}