cho.sh

Emoticons

Starting from one emoticon on screen with an empty clipboard, find the minimum seconds to reach exactly S using copy, paste, and delete-one operations.

Medium5BFSGraphDynamic programmingImplementationInterviewNo attempts yetTime limit2sMemory limit512 MB

Problem

Yeongseon is in a good mood, so she wants to send Hyobin exactly SS smile emoticons.

One emoticon is already typed on the screen. Yeongseon wants to reach SS emoticons on the screen using only the following three operations.

  1. Copy every emoticon on the screen into the clipboard.
  2. Paste every emoticon in the clipboard onto the screen.
  3. Delete one emoticon from the screen.

Each operation takes 1 second. A copy erases whatever the clipboard held before. Pasting is impossible while the clipboard is empty, and copying only part of the emoticons on the screen is impossible. Deleting only part of the emoticons in the clipboard is impossible as well. A paste adds the number of emoticons in the clipboard to the number on the screen.

Write a program that finds the minimum time Yeongseon needs to put SS emoticons on the screen.

Input

The first line contains SS. (2≤S≤10002 \le S \le 1000)

Output

Print the minimum time needed to make SS emoticons on the first line.