knapsack

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    int n,size,i,j,w,val;
    scanf("%d",&n);
    int item[n][3];
    for(i=0;i<n;i++)
    {
        item[i][0]=i+1;
        scanf("%d %d",&item[i][1],&item[i][2]);
    }
    scanf("%d",&size);
    int a[n+1][size+1];
    for(i=0;i<=n;i++)
        a[i][0]=0;
    for(i=0;i<=size;i++)
        a[0][i]=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=size;j++)
        {
            w=item[i-1][1];
            val=item[i-1][2];
            if(j-w>=0)
            {
                a[i][j]=(a[i-1][j] > a[i-1][j-w]+val ? a[i-1][j] : a[i-1][j-w]+val);
            }
            else
            {
                a[i][j]=a[i-1][j];
            }
        }
    }
    
    printf("%d",a[n][size]);
    
    return 0;
}