An đến ngân hàng để nhận số tiền là \(N\) \((500 \le N \le 100000)\), An mong muốn nhận được số tiền đó với đủ các loại mệnh giá, sao cho số tiền có mệnh giá lớn hơn phải ít hơn hoặc bằng số tiền có mệnh giá thấp hơn và tổng số tờ là ít nhất. Biết rằng có \(7\) loại mệnh giá tiền gồm: \(1,2,5,10,20,50,100\)

Yêu cầu

• Hãy giúp An tính xem phải nhận số tiền \(N\) với số tờ của mỗi loại mệnh giá.

Dữ liệu vào

• Số nguyên dương \(N\)

Dữ liệu ra

• Gồm 7 dòng, mỗi dòng gồm 2 số lần lượt là mệnh giá và số tờ. Mệnh giá tăng dần từ nhỏ đến lớn.

Input 1

1000

Output 1

1 9
2 8
5 7
10 7
20 6
50 5
100 5