# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2060
#
#   p1 > p2
# となる2つの素数で
#   p1.to_s + p2.to_s
#   p2.to_s + p1.to_s
# がまた素数だった場合に，p1とp2を接続する．(また自分自身も接続しておく）
# このとき，p1とp2で共通して接続している先が5つ以上あるとき，
# その中から5つを取り出すノードの組み合わせについて，
# 全てのノードが全てのノードに接続していれば，
# 任意の2つの素数の組み合わせにおいて別の素数が生成される．

require 'prime'
require 'set'

@@nodes = {}
def get_node(v)
  node = @@nodes[v]
  if (node)
    node
  else
    @@nodes[v] = Set.new([v])
  end
end
def connect(v1, v2)
  e1 = get_node(v1)
  e1 << v2
  e2 = get_node(v2)
  e2 << v1
  [e1, e2]
end

GROUP = 5

Prime.each do |prime|
  results = []
  s1 = prime.to_s
  
  # どちらからつなげても素数となるペアを探す
  pairs =[]
  Prime.each(prime-1).each do |prime2|
    s2 = prime2.to_s
    if ((s1 + s2).to_i.prime? && (s2 + s1).to_i.prime?)
      pairs << [s1, s2]
    end
  end
  # どちらからつなげても素数となるペアについて
  pairs.each do |c|
    # 2つのノードを接続
    e1, e2 = connect(c[0], c[1])
    # 共通している接続が5以上あれば
    if (e1.size >= GROUP && e2.size >= GROUP && (nodes = e1 & e2).size >= GROUP)
      # 5つ選んだ組み合わせにおいて
      nodes.to_a.combination(GROUP).each do |keys|
        ng_count = keys.reduce(0) {|ng_count, key|
          ng_count + ((get_node(key) & keys).size == GROUP ? 0 : 1)
        }
        if (ng_count == 0)
          # 接続先全て互いに接続している
          results << keys
        elsif (nodes.size - ng_count < GROUP)
          break
        end
      end
    end
  end
  unless (results.empty?)
    # 最小値
    puts results.map{|v| v.map(&:to_i).reduce(:+)}.min
    break
  end
end