favorite We need a little bit of your help to keep things running, click on this banner to learn more

MAP data structure

Baloo arithmetic

Balu, a lazy brown bear who teaches wolves the Law of the Jungle. He can wander where he pleases, because he eats only nuts, honey and roots.

This happened at the time when Baloo the bear taught Mowgli the Law of the Jungle. A large and important brown bear rejoiced at the abilities of a student, because wolf cubs usually learn from the Law of the Jungle only what their Pack and tribe need. But Mowgli, like a baby cub, needed to know much more.

In class on arithmetic, Baloo came up with the next game. It was necessary to get the number n from the number 1, while allowing the current number to be either multiplied by 3, or 4 to be added to the current number. For each multiplication, Baloo gave 5 cuffs, and for each addition 2 cuffs. For example,


In the first case one gets 10 cuffs, in the second case 12 cuffs.

Mowgli naturally mastered arithmetic best of all and quickly figured out how to solve a problem, having received the least amount of cuffs. He also noticed that it is not always possible to complete the task of a cunning bear ...


One integer n (1n109).


Print the minimum amount of cuffs that can be obtained for solving the problem. If the problem cannot be solved, then output number 0.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Input example #2
Output example #2
Source 2010 VII Открытый Чемпионат Харькова, I дивизион, November 28, Problem A