Phân Nhóm Tối Đa Điểm · canuc80k1519

Có $N$ thành viên được đánh số từ $1$ đến $N$ . Với mỗi cặp thành viên i, j, số nguyên $a_{i} [j]$ biểu diễn điểm nhận được nếu hai người ở cùng một nhóm. Ma trận điểm đối xứng và đường chéo bằng $0$ ; điểm có thể âm.

Hãy chia toàn bộ thành viên thành một số nhóm không rỗng, mỗi người thuộc đúng một nhóm. Tổng điểm của cách chia là tổng $a_{i} [j]$ trên mọi cặp $i < j$ nằm trong cùng nhóm.

Tìm tổng điểm lớn nhất có thể.

Input

Dòng đầu chứa số nguyên $N$ .
$N$ dòng tiếp theo, dòng thứ $i$ chứa $N$ số nguyên $a_{i, 1}, \dots, a_{i, N}$ .

Output

In tổng điểm lớn nhất.

Constraints

$1 \leq N \leq 16$ .
$- 1 0^{9} \leq a_{i} [j] \leq 1 0^{9}$ .
$a_{i} [i] = 0$ .
$a_{i} [j] = a_{j} [i]$ .

Scoring

Subtask $1$ ( $50%$ ): $N \leq 10$ .
Subtask $2$ ( $50%$ ): Không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Chia thành ${1, 2}$ và ${3}$ nhận $5$ điểm. Gom cả ba người chỉ được $5 - 4 + 2 = 3$ điểm, còn mọi cách chia khác không vượt quá $2$ .

Ý tưởng: Tiền tính score[mask], là tổng điểm của mọi cặp nằm hoàn toàn trong tập mask. Khi thêm một bit v vào tập còn lại, chỉ cần cộng các giá trị a[v][u] với u đã có.
Ý tưởng: Đặt dp[mask] là tổng điểm lớn nhất khi phân nhóm các thành viên trong mask. Lấy bit thấp nhất của mask và thử mọi nhóm sub chứa bit đó; chuyển từ dp[mask ^ sub] + score[sub]. Cố định bit thấp nhất giúp mỗi phân hoạch chỉ được xét theo một cách chọn nhóm đầu tiên.
Ý tưởng: Chứng minh đúng. Trong mọi phân hoạch của mask, thành viên mang bit thấp nhất thuộc đúng một nhóm sub. Công thức thử nhóm này và dùng lời giải tối ưu cho phần còn lại, nên không thể kém phương án tối ưu. Ngược lại, mỗi chuyển trạng thái ghép hai phần rời nhau thành một phân hoạch hợp lệ và cộng chính xác điểm nội bộ của nhóm mới. Vì vậy DP đạt đúng tổng điểm lớn nhất.
Ý tưởng: Độ phức tạp. Tiền tính O(N·2^N), DP O(3^N) thời gian và O(2^N) bộ nhớ.