题目内容

有一座巨大的官殿，可以被视为由 $n$ 行 $n$ 列房间组成，从上到下分别为第 $1,2,...n$ 行,从左到右分别为第 $1,2,...n$ 列。第 $i$ 行第 $j$ 列房间内有价值为 $a_{i,j}$ 的宝藏。

每个房间都有一扇通往下一行同一列的常开的门，即从第 $i$ 行第 $j$ 列房间能移动到第 $i+1$ 行第 $j$ 列房间，但是如果选择带走房间内的宝藏，则该侧门会关闭。特别地，第 $n$ 行的所有房间的通往下一行同一列的门都通往宫殿外。