| Submit | All submissions | Best solutions | Back to list |
EITHIEF - Trộm! |
Tân đang đi ăn trộm, Tân lẻn vào nhà thầy Ngọc, nhà thầy Ngọc có N món đồ, món đồ thứ i có Wi cân nặng và Vi giá trị, Tân chỉ có thể mang theo P cân nặng trên người!
Input
Dòng đâu tiên gồm 2 số N và P, số món đồ và số cân nặng Tân có thể vác. (1<=n <=23, 1<= P <=10^6)
N dòng tiếp theo,mỗi dòng có 2 số nguyên Wi và Vi, cân nặng và giá trị món đồ thứ i (1 <= Wi,Vi <= 10^9)
Output
Xuất ra tổng giá trị lớn nhất Tân có thể ăn cắp!
Example
Input: 5 4 1 5 1 6 1 6 2 14 3 25
Output: 31