10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

0
-1
1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 105;
int dp[MAX][MAX];
int a[MAX], b[MAX];

int main()
{
    int n, m, k, s;
    while(scanf("%d %d %d %d", &n, &m, &k, &s) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= k; i++)
            scanf("%d %d", &a[i], &b[i]);
        for(int t = 1; t <= k; t++)
            for(int i = 1; i <= s; i++)
                for(int j = m; j >= b[t]; j--)
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - b[t]] + a[t]);
        int ans = -1;
        for(int i = 0; i <= m; i++)
        {
            if(dp[s][i] >= n)
            {
                ans = i;
                break;
            }
        }
        if(ans == -1)
            printf("-1\n");
        else
            printf("%d\n", m - ans);
    }   
}