# include <bits/stdc++.h> using namespace std ; int f [200] [200] , a [105] , b [105] ; int main ( ) { int n , m , k , s ; while ( cin >> n >> m >> k >> s ) { memset ( f , 0 , sizeof ( f ) ) ; for ( int i = 1 ; i <= k ; i ++ ) { cin >> a [i] >> b [i] ; } for ( int i = 1 ; i <= k ; i ++ ) { for ( int v = 1 ; v <= s ; v ++ ) { for ( int u = b [i] ; u <= m ; u ++ ) { f [v] [u] = max ( f [v] [u] , f [v - 1] [u - b [i]] + a [i] ) ; } } } int flag = -1 ; for ( int u = 0 ; u <= m ; u ++ ) { for ( int v = 1 ; v <= s ; v ++ ) { if ( f [v] [u] >= n ) { flag = m - u ; u = m + 1 ; break ; } } } cout << flag << endl ; } return 0 ; }