Một va ly có thể chứa W đơn vị trọng lượng. Có n đồ vật mỗi vật có trọng lượng A[i] và có giá trị C[i] hỏi lên chọn mỗi loại đồ vật bao nhiêu để xếp vào valy sao cho tổng giá trị của valy là lớn nhất.

Dữ liệu vào: valy.inp

• Dòng đầu tiên là số N và W (1 ≤ N, W ≤ 100)
• Dòng thứ i trong số N dòng tiếp theo mỗi dòng ghi hai số A[i] và C[i] (1 ≤ A[i], C[i] ≤ 100)

Kết quả ra : file valy.out

• Dòng đầu tiên là tổng giá trị lớn nhất tìm được của valy
• Các dòng tiếp theo mỗi dòng ghi hai số i (là số hiệu vật được chọn) x (là số lượng chọn vật i)