-230. The Knapsack

int max(int a, int b) {
	return (a > b) ? a : b;
}

int knapsack(int n, int W, int w[21], int v[21]) {
	if (n == 0) {
		return 0;
	}
	if (w[n] > W) {
		return knapsack(n - 1, W, w, v);
	}
	else {
		return max(v[n] + knapsack(n - 1, W - w[n], w, v), knapsack(n - 1, W, w, v));
	}
}


int main() {
	int n, W, w[21], v[21];
	scanf("%d%d", &n, &W);

	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &w[i], &v[i]);
	}

	printf("%d", knapsack(n, W, w, v));
}