require 'prime'

N = gets.chomp.to_i
divs = Prime.prime_division(N).to_a
primes = divs.map(&:first)
prime_count = divs.map(&:last)

bob = prime_count.map.with_index do |c, i|
  [*0..c].map {|x| primes[i] ** x}
end

min = N - 1

bob.reduce(&:product).each do |comb|
  next if comb.is_a?(Fixnum)
  a = comb.reduce(:*)
  b = N / a
  c = a.pred + b.pred
  min = c > min ? min : c
end

puts min
