Problem Description

Author: Pote_Liu

你有 $n$ 件物品和一個容量為 $c$ 的背包。每件物品有一個重量 $w_i$ 和一個價值 $v_i$。

你只能選擇每件物品放或不放(即最多只能放一次)，求在不超過背包容量的前提下，可以取得的最大總價值是多少？

Input Format

第一列輸入兩數 $n , c$ 代表物品數量和背包容量。

接下來輸入 $n$ 行 $w_i , v_i$，代表第 $i$ 件物品的重量和價值。

Output Format

輸出可放入的最大總價值。

4 8
2 3
3 4
4 5
5 8

12

Hint

$1 \leq n \leq 10^{3} \; , \; 1 \leq c \leq 10^{5} \; , \; 1 \leq w_i , v_i \leq 10^{5}$

題解。