D問題 - Soda's Social Studies

問題文

そーだくんが通っているShizukoh高校では、ほぼ毎月テストがあります。

そーだくんは、次の社会科のテストに備えて\(N\)個の単語を覚えなければなりません（便宜上、この問題では単語\(1\), 単語\(2\),\(...\), 単語\(N\)と表します）。 そーだくんは、ある単語が他の単語と関連していそうだと思い、単語どうしを結びつけて覚えようと考えました。

\(1 \leq i < j \leq N\)とするとき、単語\(i\)と単語\(j\)を結びつけると、単語\(i\)から単語\(j\)を、また単語\(j\)から単語\(i\)を思い出せるようになります。

単語\(i\)と単語\(j\)を結びつけるのに\(T_{(i,j)}(T_{(i,j)}=T_{(j,i)}\)が成立する\()\)分を必要とする時、そーだくんが任意の単語から全ての単語を思い出せる状態にするためには、少なくとも何分必要か求めなさい。ただし、そーだくんは途中で休憩などを一切取らないものとします。

制約

• 入力は全て整数で与えられる
• \(1 < N \leq 300\)
• \(1 \leq T_{(i,j)} \leq 10^9 \quad (1 ≤ i < j ≤ N)\)

入力

入力は以下の形式で標準入力から与えられる。

\(N\)

\(T_{(1,2)}\) \(T_{(1,3)}\) \(T_{(1,4)}\) \(...\) \(T_{(1,n)}\)

\(T_{(2,3)}\) \(T_{(2,4)}\) \(...\) \(T_{(2,n)}\)

\(\vdots\)

\(T_{(n-1,n)}\)

出力

答えを整数で出力せよ。

入力例1

4
1 1 4
5 1
4

出力例1

3

• 単語\(1\)と単語\(2\)を\(1\)分で結びつけます。
• 単語\(1\)と単語\(3\)を\(1\)分で結びつけます。
• 単語\(2\)と単語\(4\)を\(1\)分で結びつけます。

以上のように結びつけることで、単語\(1\)から単語\(2\)と単語\(3\)を思い出すことができ、さらに思い出した単語\(2\)から単語\(4\)も思い出せる状態になり、目的が達成できます。 以上の操作に必要な時間は\(3\)分です。\(3\)分未満で目的を達成する方法は存在しないため、\(3\)を出力します。

入力例2

6
864 864 864 864 864
864 864 864 864
864 864 864
864 864
864

出力例2

4320

• どのように覚えても同じことがあります。
• そーだくんは三日三晩覚え続けなければなりません。可哀想に……

入力例3

4
1000000000 1000000000 1000000000
1000000000 1000000000
1000000000

出力例3

3000000000

• 答えが\(2^{32}\)分以上となることがあります。可哀想に……