# High-Capacity Knapsack
## Problem Statement
You are given $N$ items, indexed from $1$ to $N$. Each item $i$ has a weight $w_i$ and a value $v_i$. You have a knapsack with a weight capacity of $W$.
Your task is to select a subset of items such that the sum of their weights does not exceed $W$, and the sum of their values is maximized. You cannot take fractions of items; you must either take an item completely or leave it.
## Input Format
The input is given from Standard Input in the following format:
- The first line contains two integers $N$ and $W$ ($1 \le N \le 100$, $1 \le W \le 10^9$).
- The following $N$ lines each contain two integers $w_i$ and $v_i$, representing the weight and value of item $i$ ($1 \le w_i \le W$, $1 \le v_i \le 10^3$).
## Output Format
Print the maximum total value of the items you can carry in the knapsack.
## Sample Test Cases
### Sample Input 1
```
3 100
15 30
80 20
90 50
```
### Sample Output 1
```
50
```
### Sample Input 2
```
6 15
6 5
5 6
6 4
6 6
3 5
7 2
```
### Sample Output 2
```
17
```
## Constraints
- $1 \le N \le 100$
- $1 \le W \le 10^9$
- $1 \le w_i \le W$
- $1 \le v_i \le 10^3$
- All input values are integers.
- Time limit: 2 seconds
- Memory limit: 256 MB
## Explanation
**Sample 1:**
We can choose item 1 and item 2:
Total weight $= 15 + 80 = 95 \le 100$
Total value $= 30 + 20 = 50$
Alternatively, we could choose just item 3:
Total weight $= 90 \le 100$
Total value $= 50$
We cannot choose items 1 and 3 because their combined weight ($15 + 90 = 105$) exceeds $W=100$. The maximum value achievable is $50$.
**Sample 2:**
We can select items 2, 4, and 5:
Combined weights: $5 + 6 + 3 = 14 \le 15$
Combined values: $6 + 6 + 5 = 17$
This combination yields the maximum total value.
Loading problem statement...