題目描述

有n個物品需要放進一個容量為W的背包中，每個物品有其對應的重量和價值，現在需要選擇一些物品放進背包中，使得背包中物品的價值總和最大。其中每個物品只能選擇一次，不能拆分。

輸入格式

第一行輸入兩個正整數n和W，表示物品數量和背包容量，1≤n≤1000，1≤W≤10000。

接下來n行，每行輸入兩個正整數wi和vi，分別表示第i個物品的重量和價值，1≤wi≤W，1≤vi≤100。

輸出一個正整數，表示物品放入背包後的總價值。