Pecahan Uang

Diberikan sebuah nilai uang dalam dolar sebesar K. Buatlah sebuah program yang akan menghasilkan pecahan dolar bernilai total K dengan memakai uang pecahan terbesar. Jika uang pecahan terbesar tidak dapat dipakai (karena jumlah uang akan melebihi pecahan terbesar), maka diambil pecahan yang lebih kecil, dan seterusnya.

Pecahan yang tersedia adalah 1 dolar, 2 dolar, 5 dolar, 10 dolar, 20 dolar, 50 dolar, 100 dolar, 200 dolar, 500 dolar, dan 1000 dolar.

FORMAT MASUKAN

Baris pertama berisi sebuah bilangan bulat K (1 ≤ K ≤ 10 000), yang merupakan jumlah uang yang harus dipecah.

FORMAT KELUARAN

Satu atau lebih baris dimana masing-masing baris berisi dua buah bilangan bulat yang dipisahkan oleh sebuah spasi. Bilangan pertama adalah pecahan uang dan bilangan kedua adalah banyak lembar pecahan uang tersebut. Urutkanlah baris-baris berdasarkan pecahan uang, dari besar ke kecil. Pecahan uang yang tidak digunakan tidak perlu ditulis.

CONTOH MASUKAN 1

98

CONTOH KELUARAN 1

50 1
20 2
5 1
2 1
1 1

CONTOH MASUKAN 2

10000

CONTOH KELUARAN 2

1000 10