output_description: Print the minimum total weight of the edges in such a cycle.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 B_1
      A_2 B_2
      :
      A_N B_N
attempt: # -*- encoding: utf-8 -*-
  SCORE_NONE = -1
  
  
  class Life(object):
      """个体类"""
  
      def __init__(self, aGene=None):
          self.gene = aGene
          self.score = SCORE_NONE
  
  
  import random
  
  
  class GA(object):
      """遗传算法类"""
  
      def __init__(
          self,
          aCrossRate,
          aMutationRage,
          aLifeCount,
          aGeneLenght,
          aMatchFun=lambda life: 1,
      ):
          self.croessRate = aCrossRate
          self.mutationRate = aMutationRage
          self.lifeCount = aLifeCount
          self.geneLenght = aGeneLenght
          self.matchFun = aMatchFun  # 适配函数
          self.lives = []  # 种群
          self.best = None  # 保存这一代中最好的个体
          self.generation = 1
          self.crossCount = 0
          self.mutationCount = 0
          self.bounds = 0.0  # 适配值之和，用于选择是计算概率
  
          self.initPopulation()
  
      def initPopulation(self):
          """初始化种群"""
          self.lives = []
          for i in range(self.lifeCount):
              gene = [x for x in range(self.geneLenght)]
              random.shuffle(gene)
              life = Life(gene)
              self.lives.append(life)
  
      def judge(self):
          """评估，计算每一个个体的适配值"""
          self.bounds = 0.0
          self.best = self.lives[0]
          for life in self.lives:
              life.score = self.matchFun(life)
              self.bounds += life.score
              if self.best.score < life.score:
                  self.best = life
  
      def cross(self, parent1, parent2):
          """交叉"""
          index1 = random.randint(0, self.geneLenght - 1)
          index2 = random.randint(index1, self.geneLenght - 1)
          tempGene = parent2.gene[index1:index2]  # 交叉的基因片段
          newGene = []
          p1len = 0
          for g in parent1.gene:
              if p1len == index1:
                  newGene.extend(tempGene)  # 插入基因片段
                  p1len += 1
              if g not in tempGene:
                  newGene.append(g)
                  p1len += 1
          self.crossCount += 1
          return newGene
  
      def mutation(self, gene):
          """突变"""
          index1 = random.randint(0, self.geneLenght - 1)
          index2 = random.randint(0, self.geneLenght - 1)
  
          newGene = gene[:]  # 产生一个新的基因序列，以免变异的时候影响父种群
          newGene[index1], newGene[index2] = newGene[index2], newGene[index1]
          self.mutationCount += 1
          return newGene
  
      def getOne(self):
          """选择一个个体"""
          r = random.uniform(0, self.bounds)
          for life in self.lives:
              r -= life.score
              if r <= 0:
                  return life
  
          raise Exception("选择错误", self.bounds)
  
      def newChild(self):
          """产生新后的"""
          parent1 = self.getOne()
          rate = random.random()
  
          # 按概率交叉
          if rate < self.croessRate:
              # 交叉
              parent2 = self.getOne()
              gene = self.cross(parent1, parent2)
          else:
              gene = parent1.gene
  
          # 按概率突变
          rate = random.random()
          if rate < self.mutationRate:
              gene = self.mutation(gene)
  
          return Life(gene)
  
      def next(self):
          """产生下一代"""
          self.judge()
          newLives = []
          newLives.append(self.best)  # 把最好的个体加入下一代
          while len(newLives) < self.lifeCount:
              newLives.append(self.newChild())
          self.lives = newLives
          self.generation += 1
  
  
  import math
  
  
  class TSP(object):
      def __init__(
          self,
          aLifeCount=100,
      ):
          self.initCitys()
          self.lifeCount = aLifeCount
          self.ga = GA(
              aCrossRate=0.7,
              aMutationRage=0.02,
              aLifeCount=self.lifeCount,
              aGeneLenght=len(self.citys),
              aMatchFun=self.matchFun(),
          )
  
      def initCitys(self):
          self.citys = []
          n = int(input())
          for i in range(0, n):
              a, b = map(int, input().split())
              self.citys.append((a, b))
  
      def distance(self, order):
          distance = 0
          for i in range(-1, len(self.citys) - 1):
              index1, index2 = order[i], order[i + 1]
              city1, city2 = self.citys[index1], self.citys[index2]
              distance += min(city1[0], city2[1])
  
              """
                    R = 6371.004
                    Pi = math.pi 
                    LatA = city1[1]
                    LatB = city2[1]
                    MLonA = city1[0]
                    MLonB = city2[0]
                    C = math.sin(LatA*Pi / 180) * math.sin(LatB * Pi / 180) + math.cos(LatA * Pi / 180) * math.cos(LatB * Pi / 180) * math.cos((MLonA - MLonB) * Pi / 180)
                    D = R * math.acos(C) * Pi / 100
                    distance += D
                    """
          return distance
  
      def matchFun(self):
          return lambda life: 1.0 / self.distance(life.gene)
  
      def run(self, n=0):
          while n > 0:
              self.ga.next()
              distance = self.distance(self.ga.best.gene)
              # print (("%d : %f") % (self.ga.generation, distance))
              n -= 1
          print(distance)
  
  
  def main():
      tsp = TSP()
      tsp.run(10)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: Statement
  
  We have a directed weighted graph with N vertices. Each vertex has two
  integers written on it, and the integers written on Vertex i are A_i and B_i.
  
  In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq
  x,y \leq N, and its weight is {\rm min}(A_x,B_y).
  
  We will consider a directed cycle in this graph that visits every vertex
  exactly once. Find the minimum total weight of the edges in such a cycle.
samples: [{"input": "3\n    1 5\n    4 2\n    6 3", "output": "7\n    \n\nConsider the cycle 1\u21923\u21922\u21921. The weights of those edges are {\\rm\nmin}(A_1,B_3)=1, {\\rm min}(A_3,B_2)=2 and {\\rm min}(A_2,B_1)=4, for a total of\n7. As there is no cycle with a total weight of less than 7, the answer is 7.\n\n* * *"}, {"input": "4\n    1 5\n    2 6\n    3 7\n    4 8", "output": "10\n    \n\n* * *"}, {"input": "6\n    19 92\n    64 64\n    78 48\n    57 33\n    73 6\n    95 73", "output": "227"}]