INF = 1 << 29

while n = gets.to_i
  break if n == 0
  stg = n.times.map{ gets.split.map(&:to_i)
                 .map.with_index(-1) { |t, i| [t, i] }
                 .sort }

  memo = [INF] * (1<<n)
  memo[0] = 0
  (1<<n).times do |bits|
    next if memo[bits] == INF
    n.times do |i|
      next if bits | (1<<i) == bits
      nbits = bits | (1<<i)
      mint = 0
      (0..n).each do |j|
        k = stg[i][j][1]
        if k < 0 || bits | 1<<k == bits
          mint = memo[bits] + stg[i][j][0]
          break
        end
      end
      memo[nbits] = mint if memo[nbits] > mint
    end
  end
  p memo[(1<<n)-1]
end