問題
人类因被称为“巨人”的巨大生物的出现而被迫离开家园,通过搬到被城堡围墙包围的住宅区找到了暂时的安全。 然而,大约100年后,由于拥有足以摧毁城墙的力量的“巨大泰坦”的出现,人类再次面临危险。 问题是,这种“巨大的泰坦”是罕见的,我们不知道它会在何时何地出现。
城墙分为几个区域,即使巨人入侵一个区域,也可以封锁该区域,防止伤害波及其他区域。 万一巨人入侵了城墙,居民们希望建立一个道路网络,使他们能够在其余地区之间旅行,而无需经过被入侵的地区。
你的任务是找到允许你在不经过任何一个地区的情况下在所有剩余地区之间行驶的最少道路数量,以及建造这些道路的最低成本。
入力
N E_1_,_2 E_1_,_3 .. E_1_,_N_-_1 E_1_,_N E_2_,_3 E_2_,_4 .. E_2_,_N : E_N_-_2_,_N_-_1 E_N_-_2_,_N E_N_-_1_,_N
- 第一行是一个整数 N 。
请输出
- N 代表区数。
- 2 ≦ N ≦ 15 有保证。
- 从第二行开始 N 至行
在 N-1 行中,一个整数E_i_,_j 由半角空格分隔。
- E_i_,_j 是 i 第区域和 表示在第 j 个区域之间修建道路的成本。
- 1 ≦ E_i_,_j ≦ 1,000,000 有保证。
出力
入力例
4 1 5 4 2 6 3
出力例
4 10