Đổi tiền

Bạn An đang chuẩn bị đi chơi tuy nhiên bạn sợ việc sử dụng tiền tài khoản đôi khi bị nghẽn mạng sẽ không chuyển được tiền đi xe, tiền mua các nhu yếu phẩm, mua quà, ... nên bạn nhờ cửa hàng B đổi cho mình \(n\) nghìn đồng tiền tài khoản thành tiền mặt. Để tiện cầm tiền mặt, bạn An nhờ cửa hàng B đổi tiền cho mình sao cho số tờ là nhỏ nhất có thể. Em hãy giúp cửa hàng B thực hiện công việc trên, biến rằng tiền Việt Nam có các mệnh giá : 1 nghìn đồng, 2 nghìn đồng, 5 nghìn đồng, 10 nghìn đồng, 20 nghìn đồng, 50 nghìn đồng, 100 nghìn đồng, 200 nghìn đồng, 500 nghìn đồng.

Input

Đọc từ tệp DT.INP gồm một số nguyên dương duy nhất \(n\) (\(n \le 10^9\)).

Output

Ghi vào tệp DT.OUT ghi theo cấu trúc sau :

Các dòng đầu trên mỗi dòng kê mệnh giá và số tờ tiền mặt : mệnh giá trước, số tờ sau (đặt cách nhau một dấu cách trống, các mệnh giá không có tờ nào thì không kê).

Dòng cuối cùng ghi tổng số tờ.

Example

1234

500 2
200 1
20 1
10 1
2 2
7