module priority_queue
    implicit none
    integer(8), pointer:: queue(:)
    integer(8):: pend


contains
subroutine init()
    pend = 0
    allocate(queue(1))
    queue(:) = 0
end subroutine

subroutine push(n)
    integer(8):: n, self, parent, tmp
    if(size(queue) < pend+1)call append(pend)

    pend = pend + 1
    
    queue(pend) = n
    self = pend
    parent = self / 2
    if(parent == 0)return
    do while(queue(parent) > queue(self))
        tmp = queue(parent)
        queue(parent) = queue(self)
        queue(self) = tmp

        self = parent
        parent = self / 2
        if (parent == 0) exit
    end do
    ! print*, 'push', queue(1:pend)
end subroutine

function pop() result(ret)
    integer(8):: ret, c1, c2, self, tmp
    ! print*, 'pop', queue(1:pend)
    ret = queue(1)
    queue(1) = queue(pend)
    pend = pend - 1

    self = 1
    c1 = self*2
    c2 = c1 + 1
    
    if (c2 > pend)then
        if (c1 > pend) return
        if (queue(self) <= queue(c1))return
        tmp = queue(self)
        queue(self) = queue(c1)
        queue(c1) = tmp
        return
    end if 
    ! print*, 'pop2', queue(self), queue(c1), queue(c2)
    do while(queue(self) > min(queue(c1), queue(c2)))

        tmp = queue(self)
        queue(self) = min(queue(c1), queue(c2))

        if(queue(c1) >= queue(c2))then
            queue(c2) = tmp
            self = c2
        else
            queue(c1) = tmp
            self = c1
        end if

        c1 = self*2
        c2 = c1 + 1

        if (c2 > pend)then
            if (c1 > pend) return
            if (queue(self) <= queue(c1)) return
            tmp = queue(self)
            queue(self) = queue(c1)
            queue(c1) = tmp
            return
        endif
        
    end do
end function

subroutine append(x)
    integer(8), pointer:: tmp(:)
    integer(8):: x
    allocate(tmp(x))
    tmp(1:x) = queue(1:x)

    deallocate(queue)
    allocate(queue(x*2))

    queue(1:x) = tmp
    queue(x+1:) = 0
end subroutine




    
end module




program main
use priority_queue, only: init, queue, pop, push, pend
implicit none
integer(8):: N, i, count, n1, n2
call init()

read*, N
count = 0
do i = 2, int(sqrt(real(N)))
    do while(mod(N,i) == 0)
        count = count + 1
        call push(i)
        N = N / i
    end do
end do
call push(N)
count = count + 1
if (count == 1)call push(1)
do while(count > 2)
    count = count - 1
    n1 = pop()
    n2 = pop()
    call push(n1*n2)
end do

n1 = pop()
n2 = pop()

print*, n1+n2 - 2











end program