Trong siêu thị có n đồ vật (n≤1000), đồ vật thứ i có trọng lượng là W[i]≤10­00 và giá trị V[i] ≤1000. Một tên trộm đột nhập vào siêu thị, tên trộm mang theo một cái túi có thể mang được tối đa trọng lượng M (M≤1000). Hỏi tên trộm sẽ lấy đi những đồ vật nào để được tổng giá trị lớn nhất.

Giải quyết bài toán trong trường hợp sau:

• Mỗi vật chỉ được chọn một lần.

Input: 

• Dòng 1: n, M cách nhau ít nhất một dấu cách
• n dòng tiếp theo: Mỗi dòng gồm 2 số W_i, V_i, là chi phí và giá trị đồ vật thứ i.

Output: 

Ghi giá trị lớn nhất tên trộm có thể lấy