Max possible sum algorithm

Question

There are 13 arrays of 13 numbers.
Find the maximum possible sum if one number is picked from each array and each picked number should have different index e.g. first number from fifth array, second number from last array, third from eighth ...

I tried iterating with DFS but it's practically impossible since there are 13¹³ (13^13) possible combinations

If anyone could come up with a solution (probably using BFS) I would really appreciate it.

Input example:
[
[5,0,0,0,0,0,5,5,5,50,0,0,0],
[0,0,0,0,0,30,30,30,30,50,0,0,0],
[2,0,0,0,0,18,20,20,0,0,0,0,40],
[3,4,0,0,0,0,7,7,0,0,0,0,40],
[3,2,3,0,0,0,8,8,0,0,0,0,0],
[1,2,3,4,5,0,15,0,0,0,25,35,0],
[1,2,3,4,0,6,16,0,0,0,25,0,0],
[1,2,0,0,0,18,21,21,0,0,0,0,0],
[1,0,0,4,15,0,20,20,0,0,0,0,0],
[0,0,0,0,20,6,26,26,26,0,0,0,0],
[0,0,0,12,5,6,23,23,0,0,0,0,0],
[1,0,9,0,0,6,16,16,0,0,0,0,0],
[0,6,0,4,0,6,16,16,0,0,0,0,0]
]

Expected output:
3 6 9 12 15 30 21 20 26 50 25 35 40

Answer 1

Can you show your dfs code

Answer 2

YUGRAJ mine is not very neat but here it is
https://code.sololearn.com/WNIUPfqAZNL6/?ref=app