Có \(n\) người tham gia xếp hàng. Nếu người thứ \(i\) đứng ở vị trí \(j\) thì sẽ được độ thẩm mỹ là \(A_{ij}\).

Yêu cầu: Cho \(n\) và các giá trị \(A_{ij}\). Tìm cách xếp hàng có tổng độ thẩm mỹ cao nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(2 \le n \le 20\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(n\) số nguyên \(A_{i1}, A_{i2}, \dots, A_{in}\) (\(A_{ij} \le 10^9\)).

Output

• Một số nguyên duy nhất là tổng độ thẩm mỹ cao nhất tìm được.

Example

3
4 2 3
5 2 4
6 7 2

15