#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]);
 
}