Trong một nhiệm vụ giải cứu đa vũ trụ, bạn cần cử \(n\) siêu anh hùng đi canh gác tại \(n\) cổng không gian khác nhau. Tuy nhiên, mỗi siêu anh hùng lại có mức độ tương thích khác nhau với từng cổng. Cụ thể, nếu siêu anh hùng thứ \(i\) được phân công vào cổng thứ \(j\), họ sẽ tạo ra một lượng năng lượng ổn định là \(A_{i,j}\).

Yêu cầu: Hãy tìm cách phân công mỗi siêu anh hùng vào đúng một cổng (sao cho mỗi cổng đều có một người gác) để tổng năng lượng ổn định tạo ra là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \le n \le 22\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên. Số thứ \(j\) ở dòng thứ \(i\) là \(A_{i,j}\) (\(0 \le A_{i,j} \le 10^6\)).

Output

• Một số nguyên duy nhất là tổng năng lượng ổn định lớn nhất tìm được.

Example

3 
10 15 20
5 30 10
10 10 10

60

Scoring

• Subtask 1 (\(20\%\) điểm): \(n \le 8\).
• Subtask 2 (\(80\%\) điểm): \(n \le 22\).