Bài toán chia nhóm và những chú thỏ(*)

Xem PDF

Điểm: 600 Thời gian: 2.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

\(N\) con thỏ được đánh số \(1,2,3,...,N\)

Với mỗi \(i,j(1\le i,j\le N)\), độ "tâm đầu ý hợp" của con thỏ \(i\)\(j\) được kí hiệu bởi một số nguyên \(a_{i,j}\). Ở đây \(a_{i,i}=0\) với mọi \(i(1\le i\le N),a_{j,i}=a_{i,j}\) với mọi \(i,j(1\le i,j\le N)\).

\(Kaninho\) chia \(N\) con thỏ này thành nhiều nhóm. Ở đây, mỗi con thỏ thuộc về chính xác \(1\) nhóm. Sau khi chia xong, với mỗi cặp \(i,j(1\le i<j\le N)\). \(Kaninho\) sẽ kiếm được \(a_{i,j}\) điểm nếu con thỏ \(i\)\(j\) cùng thuộc về một nhóm.

Tìm số điểm tối đa mà \(Kaninho\) có thể thu được.

Input

  • Dòng thứ nhất chứa số nguyên \(N\).
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên \(a_{i,1},a_{i,2},...,a_{i,N}\) thể hiện độ "tâm đầu ý hợp" của những chú thỏ với nhau.

Output

  • In ra kết quả cần tìm.

Constraints

  • \(1\le i\le N,|a_{i,j}|\le 10^9\)
  • \(1\le N\le 16\)

Example

Test 1

Input
3
0 10 20
10 0 -100
20 -100 0 
Output
20
Note

Những con thỏ chia thành hai nhóm \((1,3),(2)\). Khi đó số điểm tối đa mà \(Kaninho\) nhận được là \(20\).


Bình luận


  • 0
    huyhau6a2 3:20 p.m. 23 Tháng 9, 2022

    đọc đề em tưởng chia thành từng cặp hóa ra chia thành từng nhóm!


    • 7
      SPyofgame 9:28 p.m. 21 Tháng 8, 2020

      Bài này mà *600** ghê vậy :v