>>948
#include<stdio.h>
#define N 5
#define WMAX 10
int main() {
  int i, j, k, l;
  int w[N] = {2,3,4,5,6}, v[N] = {4,5,8,9,11};
  int D[N+1][WMAX+1], P[N+1][WMAX+1];
  for (k = 0; k <= WMAX; ++k) D[0][k] = 0;
  for (i = 0; i < N; ++i) {
    for (k = 0; k <= WMAX; ++k) D[i+1][k] = D[i][k], P[i+1][k] = 0;
    for (k = 0; k + w[i] <= WMAX; ++k) 
      if (D[i][k+w[i]] >= D[i][k]+v[i]) D[i+1][k+w[i]] = D[i][k+w[i]];
      else D[i+1][k+w[i]] = D[i][k]+v[i], P[i+1][k+w[i]] = 1;
  }
  for (k = 0; k <= WMAX; ++k) { 
    if (!D[N][k]) continue;
    for (i = N, l = k; i-1 >= 0; --i) 
      if (P[i][l]) printf("(%d,%d) ", w[i-1], v[i-1]), l -= w[i-1];
    printf("%d %d\n", k, D[N][k]);
  }
}