1937: Гроші
Перегляд у форматі PDFМи звикли виражати грошові суми в гривнях та копійках, проте в різні часи інші народи використовували зовсім інші системи. Наприклад, до 1971 року британський фунт стерлінгів дорівнював 4 кронам, або 20 шилінгам, або 60 гроутам, або 240 пенсам. Зрозуміло, що для переведення суми, вираженої в пенсах, у більші одиниці корисним буде ланцюжок співвідношень: 1 фунт стерлінгів = 4 крони; крона = 5 шилінгів; шилінг = 3 гроути; гроут = 4 пенси. Скориставшись ним можна дізнатись, що, наприклад, 1000 пенсів = 4 фунти стерлінгів 3 шилінги 1 гроут.
Складіть програму, яка б, за відомими співвідношеннями між грошовими одиницями, суму, виражену в найменших одиницях, переводила в якомога меншу кількість більших одиниць.
Input
У першому рядку записано ціле число ~S~ - сума, виражена в найменших грошових одиницях.
У другому рядку записано ціле число ~K~ - кількість рівнів у системі грошових одиниць.
У наступних ~K~ рядках записано по одному співвідношенню між грошовими одиницями (від найбільшої до найменшої) у форматі '~H~ ~M~ ~L~', де ~H~ і ~L~ - назви, відповідно, більшої і меншої грошових одиниць; ~M~ - ціле число, кількість менших одиниць у більшій.
Output
Вивести в один рядок суму, виражену в різних одиницях відповідно до умови.
Обмеження
~1 \le S \le 1000~
~1 \le K \le 10~
~1 \le M \le 100~
~1 \le |H|, |L| \le 15~
~H~, ~L~ містять символи з проміжку ['a'..'z']
Sample Input 1
100
2
kp 5 dz
dz 12 kop
Sample Output 1
1 kp 3 dz 4 kop
Sample Input 2
1000
2
kp 10 dz
dz 10 kop
Sample Output 2
10 kp
Sample Input 3
1000
4
poundsterling 4 crown
crown 5 shilling
shilling 3 groat
groat 4 penny
Sample Output 3
4 poundsterling 3 shilling 1 groat
Коментарі
Чи може бути таке,що нам буде задано відношення а від с, б від с, але а від б не буде?
без відповіді