Chino with Queue
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Chino的数学很差，因此Cocoa非常担心。今天，Cocoa准备教Chino和排队有关的问题。
我们总是会学各种排列组合的问题，那些题目大多数都是套路。而Cocoa不喜欢套路。
通常来说，每个人在排队的时候都会对前一个人有所意见，而如果他们排在第一个，也会颇有微词。因此，排一个尽可能让更多人满意的队伍是一件难事。
假设我们要给个人排队，，表示了j排在i之前一个给i带来的舒适度，而就表示了i排在第一位的舒适度。
通过一番模拟，Chino当然计算出了最优的方案，不过Cocoa希望Chino能计算地快一点。
题目对于Chino来说太难啦，你能帮一帮Chino吗？

输入描述:

第一行是一个正整数n；接下来是一个的矩阵Wi,j

输出描述:

输出所有人舒适度之和的最大值
示例1

输入

复制 
4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

输出

复制 
13