二維背包
#include <stdio.h>
#include <string.h>
#define N 105
#define MAX(a , b) (a > b ? a : b)
int a[N], b[N], f[N][N];
int main()
{
int n, m, k, s;
while(~scanf("%d %d %d %d", &n, &m, &k, &s))
{
for(int i = 0; i < k; i++)
scanf("%d %d", &a[i], &b[i]);
memset(f, 0, sizeof(f));
int j;
for(j = 1; j <= m; j++)
{
for(int kk = 1; kk <= s; kk++)
{
for(int i = 0; i < k; i++)
{
if(j >= b[i]) f[j][kk] = MAX(f[j][kk], f[j - b[i]][kk - 1] + a[i]);
}
}
if(f[j][s] >= n) break;
}
printf("%d\n", m - j);
}
return 0;
}