В магазине продается мастика в ящиках по a кг (тип 1), b кг (тип 2) и c кг (тип 3). Как купить ровно N кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?
Входные данные
Входная строка содержит четыре числа, разделённые пробелами: a , b , c и N .
Выходные данные
В первой строке нужно вывести число K способов, которыми можно купить заданное количество мастики (N кг), не вскрывая ящики. В каждой из последующих K строчек программа должна вывести (через пробелы) три числа, ka , kb и kc : количество ящиков 1, 2 и 3 типов для каждого из K вариантов закупки. Варианты должны выводиться в лексикографическом порядке: сначала варианты с наименьшим значением ka , для одинаковых ka – сначала варианты с наименьшим значением kb и т.д.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
15 17 21 185 |
5
0 1 8
1 10 0
3 7 1
5 4 2
7 1 3 |