#!/usr/bin/env ruby input = $stdin.readlines.map(&:chomp).map{|c| c.split('/').map(&:to_i)} class BridgeFactory def initialize(pieces, bridge = [], be = 0) @pieces = pieces.dup @bridge = bridge.dup @be = be @complete = false end def complete? return @complete end def build_iter @complete = true nexts = get_nexts return nexts.map do |nxt| nbe = nxt[0] == nxt[1] ? nxt[0] : (nxt - [@be])[0] BridgeFactory.new(@pieces - [nxt], @bridge + [nxt], nbe) end end def strength return @bridge.flatten.inject(:+) || 0 end def length return @bridge.length end def to_s return "(#{strength})\t\"" + @bridge.map {|p| p.join('/') }.join('--') + "\"" end private def get_nexts return @pieces.select do |piece| piece[0] == @be || piece[1] == @be end end end bfs = [BridgeFactory.new(input)] loop do new_bfs = [] bfs.each do |bf| if !bf.complete? then new_bfs += bf.build_iter end end break if new_bfs.empty? bfs = new_bfs end puts bfs.map(&:strength).max