dp-完全背包（题）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;

#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a

int obtain[105] , reduce[105] ;
int dp[105][105] ;

int main ( ) {
    int n , m , K , s ;
    int a , b , i , j , k ;

    while ( cin >> n >> m >> K >> s ) {
        for ( i = 1 ; i <= K ; i++ ) {
            cin >> obtain[i] >> reduce[i] ;
        }

        int sign = 1 ;
        memset ( dp , 0 , sizeof(dp) ) ;
        for ( i = 1 ; i <= m ; i++ ) {
            for ( j = 1 ; j <= K ; j++ ) {
                for ( k = 1 ; k <= s ; k++ ) {
                    if ( reduce[j] <= i )
                        dp[i][k] = Max ( dp[i][k] , dp[i-reduce[j]][k-1]+obtain[j] ) ;
                }
            }
            if ( dp[i][s] >= n ) {
                cout << m-i << endl ;
                sign = 0 ;
                break ;
            }
        }
        if ( sign ) cout << -1 << endl ;
    }

    return 0 ;
}