Darwin is collecting samples at the Galapagos Islands to bring back Europe. He'd like to bring back the whole island for his research, but the Beagle has limited space!
He's choosing from $$$n\ (1 \leq n \leq 10^4)$$$ samples, each sample $$$i\ (1 \leq i \leq n)$$$ has:
- a weight $$$w_i\ (1 \leq w_i \leq 100)$$$ in kg
- relative research value $$$v_i\ (1 \leq v_i \leq 10^5)$$$
The Beagle has room for $$$m\ (0 \leq m \leq 100)$$$ kg in its main cargo hold, and features a special hold that can accommodate one item of any weight without counting towards the cargo limit.
Please output the max total research value that Darwin can bring back to the mainland.
The first line will contain two integers $$$n\ (1 \leq n \leq 10^4)$$$ and $$$m\ (0 \leq m \leq 100)$$$ — the number of samples.
The next $$$n$$$ lines will contain two integers $$$w_i\ (1 \leq w_i \leq 100)$$$ and $$$v_i\ (1 \leq v_i \leq 10^5)$$$ — the weight and relative research value for each sample.
A single integer that is the max total research value the beagle can carry.
6 102 22 22 23 13 16 3
10
