{"code":"knapsack1","name":"Bài toán ba lô 1","description":"Có $N$ viên bi, được đánh số $1,2,3,...,N$. Với mỗi $i(1\\le i\\le N)$, viên bi thứ $i$ có khối lượng là $w_i$ và có giá trị là $v_i$.\r\n\r\n$Kaninho$ quyết định chọn một số viên bi từ $N$ viên bi trên và bỏ vào ba lô để đi chơi. Sức chứa của ba lô là $W$, có nghĩa là tổng khối lượng của các viên bi được chọn phải không được quá $W$.\r\n\r\nTìm tổng giá trị lớn nhất có thể của các viên bi được chọn để bỏ vào ba lô.\r\n\r\n

Input

\r\n\r\n+ Dòng thứ nhất chứa hai số nguyên $N,W(1\\le N\\le 100,1\\le W\\le 10^5)$\r\n\r\n+ $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $w_i,v_i(1\\le w_i\\le W,1\\le v_i\\le 10^9)$\r\n\r\n

Output

\r\n\r\n+ In ra giá trị cần tìm. \r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n\r\n ```sample\r\n 3 8\r\n 3 30\r\n 4 50\r\n 5 60\r\n ```\r\n\r\n ???+ success \"Output\"\r\n\r\n ```sample\r\n 90\r\n ```\r\n \r\n ??? warning \"Note\"\r\n\r\n **Giải thích:** Viên bi thứ $1$ và $3$ sẽ được chọn để bỏ vào ba lô. Vì chúng có tổng khối lượng không quá $8$ và có giá trị lớn nhất là $90$.","points":350.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}