void dp(int *w, int *v, int n, int c){
	int **m;
	m = new int*[n+1];
	for (int i = 0; i<n + 1; i++) {
		m[i] = new int[c+1];
		for (int j = 0; j<c + 1; j++)
			m[i][j]=0;
	}
	for (int i = w[n - 1]; i <= c; i++) m[n][i] = v[n - 1];
	for (int i = n - 1; i >= 2; i--){
		for (int j = c; j >= 1; j--){
			if (j - w[i - 1] >= 0){
				int tmp = m[i + 1][j - w[i - 1]] + v[i - 1];
				m[i][j] = m[i + 1][j]>tmp ? m[i + 1][j] : tmp;
			}
			else{
				m[i][j] = m[i + 1][j];
			}
		}
	}
	if (c >= w[0]) m[1][c] = m[2][c - w[0]] + v[0];
	else m[1][c] = m[2][c];
//	for (int i = 1; i <= n; i++) {
//		for (int j = 1; j <= c; j++) cout << m[i][j] << "	";
//		cout << endl;
//	}
	int *x;
	x = new int[n+1];
	for (int i = 0; i<n + 1; i++) x[i]=0;
	if (m[1][c] == m[2][c]) x[1] = 0;
	else x[1] = 1;
	int j = c;
	for (int i = 2; i <n; i++){
		if (x[i - 1] == 0){
			if (m[i][j] == m[i + 1][j]) x[i] = 0;
			else {
				x[i] = 1;
			}
		}
		else{
			j = j - w[i - 2];
			if (m[i][j] == m[i + 1][j]) x[i] = 0;
			else {
				x[i] = 1;
			}
		}
	}
	if (m[n][c] == 0) x[n] = 0;
	else x[n] = 1;
//	for (int i = 1; i <= n; i++) cout << x[i] << "	";
	cout << endl;
}