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.

Input

• 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)~

Output

• 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~)

Sample Input

4  10
5  4
1  9
8  90
2  16

Sample Output

108
2  2
3  1