Problem Description
Oh noes! x3JiaYin the Mercedes is late with her appointment with the Black Mage! What can she do??! She can't possibly keep the Black Mage waiting!
The Black Mage is happily waiting at the next map, which can be accessed via the portal at the left of the map x3JiaYin is currently at. x3JiaYin just entered the current map and thus she is currently at the portal at the right of the map. For simplicity, portals are assumed to be of width 0 pixels and the left and right portals are L pixels apart.
Luckily, x3JiaYin has a first job skill known as Glide Blast, which allows her to move forward during a jump by tumbling with a 0-second cooldown time. However, the Black Mage has cursed her skills, thus Glide Blasting forward a non-Fibonacci number of pixels is disabled. As a result, she can only jump forward a Fibonacci number of pixels. For example, she can jump 1, 2, 3 and 5 pixels but she cannot jump 4 pixels as 4 isn't a Fibonacci number. Similarily, she can also jump 8 and 13 pixels forward since they are all Fibonacci numbers.
Each jump takes 3 seconds and x3JiaYin wants to know the minimum amount of time required for her to move from the right portal to the left portal.
Input
A single integer, L.
Output
A single integer, which denotes the time required for x3JiaYin to move from the right portal to the left portal, in seconds.
Limits
0 ≤ L ≤ 1018
Subtasks
- Subtask 1 (10%): L ≤ 1000.
- Subtask 2 (30%): L ≤ 1000000.
- Subtask 3 (60%): L ≤ 1018
Sample Input 1
5
Sample Output 1
3
Sample Input 2
12
Sample Output 2
9