금광

p. 375

 

test_case=int(input())
tc_result=[]

for _ in range(test_case):
  n,m=map(int, input().split())
  array=list(map(int, input().split()))

  d=[]
  index=0
  for i in range(n):
    d.append(array[index:index+m])
    index += m
  
  for j in range(1, m):
    for i in range(n):
      # 왼쪽 위에서 오는 경우
        if i==0:
          left_up=0
        else:
          left_up=d[i-1][j-1]
      
      # 왼쪽에서 오는 경우
        left=d[i][j-1]

      # 왼쪽 아래에서 오는 경우
        if i==n-1:
          left_down=0
        else:
          left_down=d[i+1][j-1]

      # 큰것 찾기
        d[i][j]=d[i][j]+max(left, left_up, left_down)
  
  result=0
  for i in range(n):
    result=max(result, d[i][m-1])

  tc_result.append(result)

for i in tc_result:
  print(i)