#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int f[10][10];

#define max(x, y) (x)>(y) ? (x) : (y)

int main(int argc, char** argv) {
    // 背包容量
    int package_size = 7;
    // 每个物品重量
    int weight[] = {3, 1, 3, 5, 4};
    // 每个物品价值
    int value[] =  {1, 4, 3, 6, 9};
    // 物品总数
    int vsize = sizeof(weight)/sizeof(int);

    for (int i=1; i<=vsize; i++) {
        for (int j=1; j<=package_size; j++) {
            // 如果放不下当前物品
            if (wieght[i] > j){
                // 最大价值=不选当前物品的最大价值
                f[i][j] = f[i-1][j];
            }
            // 如果可以放下当前物品
            else {
                // 最大价值=max(不选当前物品的最大价值,重量减少后的最大价值+当前物品价值)
                f[i][j] = max(f[i-1][j], f[i-1][j-weight[i]]+value[i]);
            }
        }
    }
    printf("%d\n", f[vsize][package_size]);
    
}