#!/usr/bin/env ruby

require "prime"

def factors(m)
  return [1] if 1 == m
  primes, powers = Prime.prime_division(m).transpose
  ranges = powers.map { |n| (0..n).to_a }
  ranges[0]
    .product( *ranges[1..-1] )
    .map { |es| primes
                .zip(es)
                .map { |p, e| p ** e }
                .reduce(:*)
    }.sort
end

target = File.read("day20.input").strip.to_i

i = 1
loop do
  break if factors(i).sum * 10 >= target
  i += 1
end
puts i