小老鼠们一年一度的运动会开始啦！他们提前一分钟拿到了一张有N*N（N<100）个草方格的图，并标注出了里面奶酪的数量（每个方格中奶酪数量不一定相同，未标注代表0个），小老鼠们只有两次机会从左上角走到右下角，且每次只能往右走一格，或者向下走一格，但是在走过的路上可以拿走对应方格里的奶酪（拿走后奶酪数变成0）。信信想要拿到最多的奶酪，可是一分钟的思考时间远远不够，你可以编个程序帮助他找出两条这样的路径，使得所得到的奶酪数最多吗？
小老鼠们一年一度的运动会开始啦！他们提前一分钟拿到了一张有N*N（N<100）个草方格的图，并标注出了里面奶酪的数量（每个方格中奶酪数量不一定相同，未标注代表0个），小老鼠们只有两次机会从左上角走到右下角，且每次只能往右走一格，或者向下走一格，但是在走过的路上可以拿走对应方格里的奶酪（拿走后奶酪数变成0）。信信想要拿到最多的奶酪，可是一分钟的思考时间远远不够，你可以编个程序帮助他找出两条这样的路径，使得所得到的奶酪数最多吗？
第一行为一个整数N，代表草方格数N*N。
接下来每行三个整数，前两个整数代表位置，后面一个整数代表该位置的奶酪数。
一行单独的0表示输入结束。
一个整数，表示所能的得到的最多奶酪数。
8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0
67
左上角第一个为 1 1