Problem:


苗木

 植物学者のサトー博士は苗木用の特殊肥料を何種類も発明しました。その肥料を苗木に与えると、瞬く間に苗木の大きさが変わります。
 但し、肥料に以下のように副作用があることが判明しました。

1 回目に与えた肥料だけでは、苗木の大きさが変わりません。

2 回目以降は、その回に与えた肥料と、その直前に与えた肥料との組み合わせによって苗木に影響を与えます。良い影響を与えると苗木が伸び、悪い影響を与えると苗木が縮んでしまうこともあります。

試しに、サトー博士は 3 種類の肥料 (肥料 1、2、3) に対し、ある時点で与えた肥料 (今回の肥料) とその直前に与えた肥料 (直前の肥料) の組み合わせによる苗木の成長度合いを調べ、以下の「成長度表」を作成しました。

 右表の 1 行目は今回与える肥料の番号で、1 列目はその直前に与えた肥料の番号です。他の数字は直前に与えた肥料と今回与える肥料の組み合わせによる苗木の成長度 (成長後対成長前の大きさの比率) を示します。成長度 > 1.0 の場合は苗木が伸びる、成長度 < 1.0 の場合は苗木が縮むことを示します。例えば肥料 1 の後に肥料 2 を与えると苗木の大きさが 3 倍になるが、肥料 1 の後に肥料 3 を与えると苗木の大きさが半分に縮んでしまいます。

 苗木に与える肥料の回数が制限された場合、苗木をできるだけ大きく育てるにはどの肥料をどのような順で与えればよいでしょうか?「成長度表」がその答え教えてくれます。例として上の表にある肥料を 3 回だけ与える場合、以下のように肥料 3 → 肥料 1 → 肥料 2 の順にあげると最も苗木が成長します。

 1 回目の肥料 (肥料 3) では苗木の大きさは変わりません。

 2 回目の肥料 (肥料 1) では、表より肥料 3 後の肥料 1 での成長度が 3.0 なので、苗木の大きさは前回の 3.0 倍になります。

 3 回目の肥料 (肥料 2) では、表より肥料 1 後の肥料 2 での成長度が 3.0 なので、苗木の大きさはさらに前回の 3.0 倍で、最初の 3.0 &times; 3.0 の 9.0 倍になります。

今度は、サトー博士は発明した n 種類の肥料を全部調べて、上のような「成長度表」を作りあげましたが、非常に大きな表になってしまい、肥料の種類と与える順番を決めるのに大変苦労しています。

 そこで博士に代わり、n 種類の肥料の組み合わせによる苗木の「成長度表」中の成長度値部分を入力とし、肥料を m  回与えた後の最大の苗木の大きさを求めるプログラムを作成してください。ただし、初めの苗木の大きさを 1 とし、1 回目に与える肥料の成長度はどの肥料でも 1.0 とします。なお、肥料は 1 から n まで番号付けされています。

Input

 複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下の形式で与えられます。

n m
g11 g12 ... g1n
g21 g22 ... g2n
:
gn1 gn2 ... gnn

1 行目に肥料の種類数 n (2 ≤ n ≤ 100)、 肥料を与える回数 m (1 ≤ m ≤ 100) が与えられます。

続くn 行に、肥料 i の後に肥料 j を与えた時の苗木の成長度 gij (0.0 ≤ gij ≤ 10.0, 実数) が与えられます。

データセットの数は 20 を超えません。

Output

データセット毎に、最大の苗木の大きさを１行に出力します。出力する苗木の大きさは、小数点第 3 位を四捨五入して、小数点第 2 位まで求めてください。

Sample Input

3 3          
1.3 3.0 0.5 
2.4 2.1 1.0
3.0 0.8 1.2
2 2
1.0 1.0
1.0 1.0
0 0

Output for the Sample Input

9.00
1.00



Sample input:
3 3
1.3 3.0 0.5
2.4 2.1 1.0
3.0 0.8 1.2
2 2
1.0 1.0
1.0 1.0
0 0


Sample output:
9.00
1.00

Submission status: Wrong Answer

Solution code:
while 1:
    n,m = map(int,raw_input().split())
    if n == m == 0: break
    g = [map(float,raw_input().split()) for _ in range(n)]
    grow = [[0.0]*n for _ in range(m)]
    for i in range(n): grow[0][i] = 1.0
    for day in range(1,m):
        for i in range(n):
            for j in range(n):
                grow[day][j] = max(grow[day][j], grow[day-1][i]*g[i][j])
    print max(max(grow[day]) for day in range(m))

Submission status: Wrong Answer

Solution code:
while 1:
    n,m = map(int,raw_input().split())
    if n == m == 0: break
    g = [map(float,raw_input().split()) for _ in range(n)]
    grow = [[0.0]*n for _ in range(m)]
    for i in range(n): grow[0][i] = 1.0
    
    for day in range(1,m):
        for prev in range(n):
            for cur in range(n):
                grow[day][cur] = max(grow[day][cur], grow[day-1][prev]*g[prev][cur])
                
    print round(max(max(grow[day]) for day in range(m)),2)

Submission status: Wrong Answer

Solution code:
while 1:
    n,m = map(int,raw_input().split())
    if n == m == 0: break
    g = [map(float,raw_input().split()) for _ in range(n)]
    grow = [[0.0]*n for _ in range(m)]
    for i in range(n): grow[0][i] = 1.0
    
    for day in range(1,m):
        for prev in range(n):
            for cur in range(n):
                grow[day][cur] = max(grow[day][cur], grow[day-1][prev]*g[prev][cur])
                
    print round(max(max(grow[day]) for day in range(m)),3)

Submission status: Wrong Answer

Solution code:
while 1:
    n,m = map(int,raw_input().split())
    if n == m == 0: break
    g = [map(float,raw_input().split()) for _ in range(n)]
    grow = [[0.0]*n for _ in range(m)]
    for i in range(n): grow[0][i] = 1.0
    
    for day in range(1,m):
        for cur in range(n):
            for prev in range(n):
                grow[day][cur] = max(grow[day][cur], grow[day-1][prev]*g[prev][cur])
                
    print round(max(grow[m-1]),3)

Submission status: Wrong Answer

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0): break
    fert = [map(float, raw_input().split()) for _ in range(N)]
    dp = [[0]*N for _ in range(M)]
    for i in range(N): dp[0][i] = 1.0
    for i in range(M-1):
        for j in range(N):
            dp[i+1][j] = max([dp[i][k]*fert[k][j] for k in range(N)])
    print('{:.2f}'.format(int(max(dp[M-1])*100+0.5)/100))

Submission status: Wrong Answer

Solution code:
while 1:
	n, m = map(int,raw_input().split(" "))
	if n == m == 0:
		break
	fert = [map(float,raw_input().split(" ")) for i in range(n)]
	dp = [[1. for i in range(n)]] + [[0. for i in range(n)] for i in range(m-1)]
	for i in range(m-1):
		for j in range(n):
			for k in range(n):
				tmp = dp[i][j] * fert[j][k]
				if tmp > dp[i+1][k]:
					dp[i+1][k] = tmp
	print max(dp[m-1])

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n==0:
        exit(0)
    nxt = []
    append = nxt.append
    for i in xrange(n):
        fs = map(float, raw_input().split())
        idx = 0; mf = -1.0
        for j, f in enumerate(fs):
            if mf < f:
                mf = f; idx = j
        append((j, mf))

    if m==1:
        print "1.0"
    else:
        ans = 0.0
        for i in xrange(n):
            r = 1.0; state = i
            for j in xrange(m-1):
                state, val = nxt[state]
                r *= val
            ans = max(ans, r)
        print round(ans, 2)

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n==0:
        exit(0)
    mat = [map(float, raw_input().split()) for i in xrange(n)]
    dp = [1.0] * n

    if m==1:
        print "1.0"
    else:
        for t in xrange(m-1):
            dp2 = [1.0] * n
            for i in xrange(n):
                r = -1.0
                mat_i = mat[i]
                for j in xrange(n):
                    r = max(r, dp[j] * mat_i[j])
                dp2[i] = r
            dp = dp2
        print round(max(dp), 2)

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n==0:
        exit(0)
    mat = [map(float, raw_input().split()) for i in xrange(n)]
    dp = [1.0] * n

    if m==1:
        print "1.0"
    else:
        for t in xrange(m-1):
            dp2 = [-1.0] * n
            for i in xrange(n):
                mat_i = mat[i]
                for j in xrange(n):
                    dp2[j] = max(dp2[j], dp[i] * mat_i[j])
            dp = dp2
        print round(max(dp), 2)

Submission status: Wrong Answer

Solution code:
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    g=[map(float,raw_input().split()) for _ in xrange(n)]
    dp=[[0.0]*n for _ in xrange(m+1)]
    for j in xrange(n):
        dp[0][j]=1.0
    for i in xrange(m):
        for j in xrange(n):
            for k in xrange(n):
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]*g[k][j])
    print(max(dp[m-1]))

Submission status: Wrong Answer

Solution code:
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    g=[map(float,raw_input().split()) for _ in xrange(n)]
    dp=[[0.0]*n for _ in xrange(m+1)]
    for j in xrange(n):
        dp[0][j]=1.0
    for i in xrange(m):
        for j in xrange(n):
            for k in xrange(n):
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]*g[k][j])
    print(round(max(dp[m-1]),2))

Submission status: Wrong Answer

Solution code:
def my_round(f):
  x, y = str(f).split(".")
  if len(y) <= 2:
    return x + "." + y + "0" * (2 - len(y))
  if y[2] >= "5":
    z = float(x + "." + y[:2]) + 0.01
  else:
    z = float(x + "." + y[:2])
  l, r = str(z).split(".")
  return l + "." + r + "0" * (2 - len(r))

while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  gs = [list(map(float, input().split())) for _ in range(n)]
  dp = [[0] * n for _ in range(m + 1)]
  for i in range(n):
    dp[1][i] = 1.0
  for i in range(2, m + 1):
    for j in range(n):
      dp[i][j] = max([dp[i - 1][k] * gs[k][j] for k in range(n)])
  print(my_round(max(dp[m])))

Submission status: Wrong Answer

Solution code:
import random
def my_round(f):
  x, y = str(f).split(".")
  if len(y) <= 2:
    return x + "." + y + "0" * (2 - len(y))
  if y[2] >= "5":
    z = float(x + "." + y[:2]) + 0.01
  else:
    z = float(x + "." + y[:2])
  l, r = str(z).split(".")
  if len(r) <= 2:
    return l + "." + r + "0" * (2 - len(r))
  else:
    return l + "." + r[:2]
"""
def test(f):
  print(f, my_round(f))

for _ in range(1000):
  r = random.random()
  test(r)
"""
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  gs = [list(map(float, input().split())) for _ in range(n)]
  dp = [[0] * n for _ in range(m + 1)]
  for i in range(n):
    dp[1][i] = 1.0
  for i in range(2, m + 1):
    for j in range(n):
      dp[i][j] = max([dp[i - 1][k] * gs[k][j] for k in range(n)])
  print(my_round(max(dp[m])))

Submission status: Wrong Answer

Solution code:
#coding:utf-8
from __future__ import division,print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの

# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=916014

# N * Mの表をつくる.すべての要素はvにする。
def make_matrix(N,M,v):
    # return [[v for i in range(M)] for j in range(N)]とも書ける。
    ret = []
    for i in range(N):
        l = []
        for j in range(M):
            l.append(v)
        ret.append(l)
    return ret


# gは行列(二次元配列)
def solve(n,m,g):
    # current_max[i][j] = 直前がjの場合のi日目の最大成長度
    # 負の数にはなりえない。
    current_max = make_matrix(m,n,-1)
    # 最初は何をあげても1.0のまま
    for i in range(n):
        current_max[0][i] = 1.0
    for i in range(1,m):
        # jは次にあげるもの
        for j in range(n):
            # 前に何をあげてたか
            # current_max[i][j] = max(current_max[i-1][k] * g[k][j]) for k in [0,n]
            for k in range(n):
                current_max[i][j] = max(current_max[i][j],
                                        current_max[i-1][k]*g[k][j])
    ret = max(current_max[m-1])
    ret = round(ret,2)
    print(ret)

def main():
    while True:
        # 受けとった文字列をintに変換する(リストの内包表記)
        n,m = [int(i) for i in input().split(" ")]
        if n == 0 and m == 0:
            return
        g = []
        for i in range(n):
            g.append([float(x) for x in input().split(" ")])

        solve(n,m,g)
main()

Submission status: Accepted

Solution code:
while 1:
    n,m = map(int,raw_input().split())
    if n == m == 0: break
    g = [map(float,raw_input().split()) for _ in range(n)]
    grow = [[0.0]*n for _ in range(m)]
    for i in range(n): grow[0][i] = 1.0
    
    for day in range(1,m):
        for cur in range(n):
            for prev in range(n):
                grow[day][cur] = max(grow[day][cur], grow[day-1][prev]*g[prev][cur])
                
    print "%.2f"%round(max(grow[m-1]),3)

Submission status: Accepted

Solution code:
while True:
    N, M = map(int, raw_input().split())
    if (N, M) == (0, 0): break
    fert = [map(float, raw_input().split()) for _ in range(N)]
    dp = [[0]*N for _ in range(M)]
    for i in range(N): dp[0][i] = 1.0
    for i in range(M-1):
        for j in range(N):
            dp[i+1][j] = max([dp[i][k]*fert[k][j] for k in range(N)])
    print('{:.2f}'.format(max(dp[M-1])))

Submission status: Accepted

Solution code:
while 1:
	n, m = map(int,raw_input().split(" "))
	if n == m == 0:
		break
	fert = [map(float,raw_input().split(" ")) for i in range(n)]
	dp = [[0. for i in range(n)] for i in range(m)]
	dp[0] = [1. for i in range(n)]
	for i in range(m-1):
		for j in range(n):
			for k in range(n):
				tmp = dp[i][j] * fert[j][k]
				if tmp > dp[i+1][k]:
					dp[i+1][k] = tmp
	print "{0:.2f}".format(round(max(dp[m-1]), 2))

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n==0:
        exit(0)
    mat = [map(float, raw_input().split()) for i in xrange(n)]
    dp = [1.0] * n
    for t in xrange(m-1):
        dp2 = [-1.0] * n
        for i in xrange(n):
            mat_i = mat[i]; dp_i = dp[i]
            for j in xrange(n):
                dp2[j] = max(dp2[j], dp_i * mat_i[j])
        dp = dp2
    print "%.02f" % round(max(dp), 2)

Submission status: Accepted

Solution code:
while 1:
    n,m=map(int,raw_input().split())
    if n==m==0:break
    g=[map(float,raw_input().split()) for _ in xrange(n)]
    dp=[[0.0]*n for _ in xrange(m)]
    for j in xrange(n):
        dp[0][j]=1.0
    for i in xrange(m-1):
        for j in xrange(n):
            for k in xrange(n):
                dp[i+1][j]=max(dp[i+1][j],dp[i][k]*g[k][j])
    print("%.2f" % round(max(dp[m-1]),2))

Submission status: Accepted

Solution code:
# Aizu Problem 0191: Baby Tree
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n, m = [int(_) for _ in input().split()]
    if n == m == 0:
        break
    rates = [[float(_) for _ in input().split()] for __ in range(n)]
    growth = [[0.] * n for _ in range(m)]
    for k in range(n):
        growth[0][k] = 1.
    for day in range(1, m):
        for current in range(n):
            for previous in range(n):
                growth[day][current] = max(growth[day][current], \
                                    growth[day-1][previous] * rates[previous][current])
    print("%.2f" % max(growth[m-1]))

Submission status: Accepted

Solution code:
# AOJ 0191: Baby Tree
# Python3 2018.6.20 bal4u

while True:
	n, m = list(map(int, input().split()))
	if n == 0: break
	d =  [[0.0 for j in range(n)] for i in range(n)]
	for i in range(n): d[i] = list(map(float, input().split()))
	dp =  [[0.0 for j in range(n)] for k in range(m)]
	for i in range(n): dp[0][i] = 1
	for k in range(1, m):
		for i in range(n):
			for j in range(n):
				dp[k][j] = max(dp[k][j], dp[k-1][i]*d[i][j])
	ans = 0
	for i in range(n):
		if dp[m-1][i] > ans: ans = dp[m-1][i]
	print(format(ans, ".2f"))

Submission status: Accepted

Solution code:
while True:
  n, m = map(int, input().split())
  if n == 0:
    break
  gs = [list(map(float, input().split())) for _ in range(n)]
  dp = [[0] * n for _ in range(m + 1)]
  for i in range(n):
    dp[1][i] = 1.0
  for i in range(2, m + 1):
    for j in range(n):
      dp[i][j] = max([dp[i - 1][k] * gs[k][j] for k in range(n)])
  print(format(max(dp[m]), ".2f"))

Submission status: Accepted

Solution code:
#coding:utf-8
from __future__ import division,print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの


# N * Mの表をつくる.すべての要素はvにする。
def make_matrix(N,M,v):
    # return [[v for i in range(M)] for j in range(N)]とも書ける。
    ret = []
    for i in range(N):
        l = []
        for j in range(M):
            l.append(v)
        ret.append(l)
    return ret


# gは行列(二次元配列)
def solve(n,m,g):
    # current_max[i][j] = 直前がjの場合のi日目の最大成長度
    current_max = make_matrix(m,n,-1)
    # 最初は何をあげても1.0のまま
    for i in range(n):
        current_max[0][i] = 1.0
    for i in range(1,m):
        # jは次にあげるもの
        for j in range(n):
            # 前に何をあげてたか
            for k in range(n):
                current_max[i][j] = max(current_max[i][j],
                                        current_max[i-1][k]*g[k][j])
    ret = max(current_max[m-1])
    ret = round(ret,3)
    print("%.2f" % ret)

def main():
    while True:
        # 受けとった文字列をintに変換する(リストの内包表記)
        n,m = [int(i) for i in input().split(" ")]
        if n == 0 and m == 0:
            return
        g = []
        for i in range(n):
            g.append([float(x) for x in input().split(" ")])

        solve(n,m,g)
main()

Submission status: Accepted

Solution code:
#coding:utf-8
from __future__ import division,print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの

# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=916014

# N * Mの表をつくる.すべての要素はvにする。
def make_matrix(N,M,v):
    # return [[v for i in range(M)] for j in range(N)]とも書ける。
    ret = []
    for i in range(N):
        l = []
        for j in range(M):
            l.append(v)
        ret.append(l)
    return ret


# gは行列(二次元配列)
def solve(n,m,g):
    # current_max[i][j] = 直前がjの場合のi日目の最大成長度
    # 負の数にはなりえない。
    current_max = make_matrix(m,n,-1)
    # 最初は何をあげても1.0のまま
    for i in range(n):
        current_max[0][i] = 1.0
    for i in range(1,m):
        # jは次にあげるもの
        for j in range(n):
            # 前に何をあげてたか
            # current_max[i][j] = max(current_max[i-1][k] * g[k][j]) for k in [0,n]
            for k in range(n):
                current_max[i][j] = max(current_max[i][j],
                                        current_max[i-1][k]*g[k][j])
    ret = max(current_max[m-1])
    ret = round(ret,3)
    print("%.2f" % ret)

def main():
    while True:
        # 受けとった文字列をintに変換する(リストの内包表記)
        n,m = [int(i) for i in input().split(" ")]
        if n == 0 and m == 0:
            return
        g = []
        for i in range(n):
            g.append([float(x) for x in input().split(" ")])

        solve(n,m,g)
main()

Submission status: Accepted

Solution code:
#coding:utf-8
from __future__ import division,print_function
try:
    input = raw_input
    range = xrange
except NameError:
    pass
# 上記のコードはPython2とPython3の違いを一部吸収するためのもの

# http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=916014

# N * Mの表をつくる.すべての要素はvにする。
def make_matrix(N,M,v):
    # return [[v for i in range(M)] for j in range(N)]とも書ける。
    ret = []
    for i in range(N):
        l = []
        for j in range(M):
            l.append(v)
        ret.append(l)
    return ret


# gは行列(二次元配列)
def solve(n,m,g):
    # current_max[i][j] = 直前がjの場合のi日目の最大成長度
    # 負の数にはなりえない。
    current_max = make_matrix(m,n,-1)
    # 最初は何をあげても1.0のまま
    for i in range(n):
        current_max[0][i] = 1.0
    for i in range(1,m):
        # jは次にあげるもの
        for j in range(n):
            # 前に何をあげてたか
            # current_max[i][j] = max(current_max[i-1][k] * g[k][j]) for k in [0,n]
            for k in range(n):
                current_max[i][j] = max(current_max[i][j],
                                        current_max[i-1][k]*g[k][j])
    ret = max(current_max[m-1])
    ret = round(ret,2)
    print("%.2f" % ret)

def main():
    while True:
        # 受けとった文字列をintに変換する(リストの内包表記)
        n,m = [int(i) for i in input().split(" ")]
        if n == 0 and m == 0:
            return
        g = []
        for i in range(n):
            g.append([float(x) for x in input().split(" ")])

        solve(n,m,g)
main()

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
#MOD = 1000000007
MOD = 10000
EPS = 0.000000001
sys.setrecursionlimit(100000)


while True:

    N,M = map(int,input().split())
    if N == 0 and M == 0:
        break

    table = [list(map(float,input().split())) for _ in range(N)]

    dp = [[0]*N for _ in range(M)]
    for i in range(N):
        dp[0][i] = 1.0

    for i in range(1,M): #回数のループ
        for k in range(N):
            for p in range(N):
                dp[i][p] = max(dp[i][p],dp[i-1][k]*table[k][p])

    ans = 0.0
    for i in range(N):
        ans = max(ans,dp[M-1][i])

    print("%.2f"%(ans))

Submission status: Runtime Error

Solution code:
from math import sqrt
prime = [1 for _ in xrange(10**6+1)]
prime[1] = 1
prime[0] = 0
for i in xrange(2, int(sqrt(10**6+1))+1):
    if prime[i] == 1:
        for j in xrange(i+i, 10**6+1, i):
            prime[j] = 0
while True:
    N, X = map(int, raw_input().split())
    if (N, X) == (0, 0): break
    price = [input() for _ in xrange(N)]
    dp = [0] * (X+1)
    dp[0] = 1
    for i in xrange(X+1):
        if dp[i] == 0: continue
        for p in price:
            if i + p <= X:
                dp[i+p] = 1
    for i in xrange(X, -1, -1):
        if i > 0 and dp[i] == 1 and prime[i] == 1:
            print(i)
            break
    else:
        print("NA")

Submission status: Runtime Error

Solution code:
# AOJ 0191: Baby Tree
# Python3 2018.6.20 bal4u

while True:
	n, m = list(map(int, input().split()))
	if n == 0: break
	d =  [[0.0 for j in range(n)] for i in range(n)]
	for i in range(n): d[i] = list(map(float, input().split()))
	dp =  [[0.0 for j in range(n)] for i in range(n)]
	for i in range(n): dp[0][i] = 1
	for k in range(1, m):
		for i in range(n):
			for j in range(n):
				dp[k][j] = max(dp[k][j], dp[k-1][i]*d[i][j])
	ans = 0
	for i in range(n):
		if dp[m-1][i] > ans: ans = dp[m-1][i]
	print(format(ans, ".2f"))