def main():
    L=int(input())
    if L==1 or L==2 or L==3:
        print(0)
        return
    primenum=[]
    def isprime(num): #質數篩法有待改進
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        return True
    for i in range(2,L+1):
        if isprime(i):
            primenum.append(i)
    
    dp=[0,0,0,0]+[float('inf')]*(L-3)
    for i in range(4,L+1):
        for j in primenum:
            if j>=i:
                break
            if i-j not in primenum: #用二分搜更好
                continue
            dp[i]=min(dp[i],dp[j]+dp[i-j]+i)
        if dp[i]==float('inf'):

            dp[i]=0
        continue
    print(dp[L])
main()