A - 特別作戦 解説 /

実行時間制限: 2 sec / メモリ制限: 256 MB

問題

巨大生物「巨人」の出現によりに住居を追われた人類は、城壁に囲まれた居住区に移り住むことで一時的な安全を得るに至った。 しかしそれから約１００年後、城壁を破壊する程の力を持つ「超大型巨人」の出現により人類は再びの危険に晒されることとなる。 困ったことにこの「超大型巨人」は神出鬼没であり、いつ何時どこに現れるかわからない。

城壁内はいくつかの地区に分かれており、仮にある一つの地区に巨人が侵入してもその地区を封鎖することで他の地域に被害が及ぶのを防ぐことができる。 住人達は万が一城壁内に巨人が侵入した場合に備えて、侵入された地区を通らずに残りの地区間を移動できるような道路網を整備したいと考えた。

あなたの仕事は任意の１地区を通らなくても残りの全地区間を移動できるような道路の最小本数と、そのような道路を整備するのにかかる最小コストを求めることである。

入力

入力は以下の形式で標準入力から与えられる。 
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
  1. 1行目には整数 N が与えられます。
    • N は地区の数を表します。
    • 2 ≦ N ≦ 15 であることは保証されています。
  2. 2行目から 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

出典

Maximum-Cup 2013