Expression Representation

Time limit2sMemory limit128 MB

Summary
Compute the minimum number of 1-symbols needed to build an integer n using +, *, ! and parentheses, using DP over factorial and multiplicative decompositions.
Level

Medium7 of 10

Topics
Dynamic programming, Math, Number theory
Solved
No attempts yet

Problem

An expression representation is an expression made only from the symbol 1, the operators +, *, !, and parentheses (, ). It is defined by the following rules.

  1. 1 is an expression representation.
  2. If e is an expression representation, then (e) and e! are also expression representations.
  3. If e1 and e2 are expression representations, then e1+e2 and e1*e2 are also expression representations.

For example, expressions with value 18 include (1+1+1)*(1+1+1)! and (1+1+1+1)*(1+1+1)+(1+1+1)!.

Given an integer n, find the minimum number of 1 symbols needed by any expression representation whose value is n.

Input

The first line contains an integer n.

  • 1 ≤ n ≤ 10,000

Output

Print the minimum number of 1 symbols needed to make an expression representation with value n.

Hint

18 = (1+1+1)*(1+1+1)!

Examples1

  1. Example 1

    Input
    18
    Expected output
    6