背景

每个人其实都是熊孩子 只是因为充要条件不足够。

描述

每个人小时候都是熊孩子,至少在遇到命中注定的好基友的时候也会产生于等同熊孩子的破坏力。

你辛苦搜集而来的资料展现出这样的一个规律:每一个小朋友都有一个特征值与破坏值。如果两个小朋友的特征值以及破坏值都比较接近,即的话我们称这两个小朋友的相性十分好,他们在一起玩的时候会产生的破坏值。为了简化问题,我们假设每次只能有两个小朋友在一起玩。

现在你遇到了这样的一个难题:如果有一对相性很好的小朋友没有互相传递过愉悦的话,他的父母就会以他们的孩子受了冷落为由开动阿姆斯特朗回旋加速喷气式阿姆斯特朗回旋加速喷气炮来干掉你。为了防止这一人间 喜剧 惨剧的发生,你需要传递给其中任意一个小 炮友 朋友愉悦感,随后这个小朋友可以通过做游戏将愉悦感传递给一个与他相性很好的小朋友。

反复互相传递愉悦后,我们需要保证:最后必须是你所传递的小朋友获得愉悦。

由于根据你第一次选中的小朋友的不同,产生的破坏值总和ANS也会不同,因此请求出ANS之中的最小值。输入保证,对于任意一对小朋友,总有一种方案能使得他们能够直接或间接传递愉悦。

一对小朋友可以多次传递愉悦!

输入格式

第一行为一个整数N,代表小朋友的数目。

第二行至第N+1行每行有两个数,依次分别为特征值,破坏值

输出格式

一个整数,表示ANS之中的最小值。

样例输入

2
1 2
2 3

样例输出

6

数据范围与约定

对于100%的数据,

测试点序号 N不大于  其他特征
1          2        
2          7        
3          20      
4          1000     1≤f[i],d[i]≤1000
5          2000000  1≤f[i],d[i]≤1000
6          2000000  f[i]=1  任意一对小朋友不经过重复人传递愉悦的途径只有一种
7          1000     任意一对小朋友不经过重复人传递愉悦的途径只有一种
8          1000     任意一对小朋友不经过重复人传递愉悦的途径有且只有两种
9          1000     能够传给奇数个小朋友愉悦的小朋友不超过2个
10         1000     能够传给奇数个小朋友愉悦的小朋友不超过20个

样例解释

因为,所以从小朋友1到小朋友2可以传递愉悦,代价是max(2,3)=3点破坏值;当然因为,所以从小朋友2到小朋友1也可以传递愉悦,代价是max(3,2)=3点破坏值。你可以先传给1号小朋友愉悦,然后令小朋友1传给小朋友2愉悦,造成3破坏值。现在任何一对能传递愉悦的小朋友都传递过愉悦了,但由于必须令愉悦回到小朋友1,所以还需要造成3破坏值使得愉悦回到小朋友1。当然也可以先传给小朋友2愉悦,破坏值总和也是6。无论如何,可以证明,这是破坏值总和最小的方案,所以输出6。

来源

原创

不得不说

这可真是一道充满了愉♂悦的良心题呢...