Trộm bản vẽ

Cho một đồ thị vô hướng có $n$ đỉnh đánh số từ $1$ đến $n$. Mỗi cặp đỉnh $(i,j)$ có thể có một cạnh nối với trọng số $c_{i,j}$ không âm, hoặc không có cạnh.

Đồ thị này có một tính chất đặc biệt: với mọi tập $k$ đỉnh $S\subseteq \{1,2,\dots ,n\}$, tồn tại duy nhất một đỉnh không thuộc $S$ kề với tất cả các đỉnh trong $S$ (gọi đỉnh này là kề với $S$). Dữ liệu đảm bảo đồ thị thỏa tính chất này.

Với mỗi tập $S$ kích thước $k$, gọi $t$ là đỉnh kề với $S$. Định nghĩa độ nguy hiểm của $S$ là: $$D(S)=\sum _{v\in S}{c}_{v,t}.$$

Hãy tính trung bình cộng độ nguy hiểm trên tất cả $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ tập $S$ có kích thước $k$, làm tròn xuống đến số nguyên gần nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$.
• Trong $n-1$ dòng tiếp theo, dòng thứ $i$ chứa $n-i$ số nguyên $c_{i,i+1},c_{i,i+2},\dots ,c_{i,n}$. Nếu $c_{i,j}=-1$ thì hai đỉnh $i$ và $j$ không có cạnh nối, ngược lại $c_{i,j}$ là trọng số cạnh.

Dữ liệu ra

In ra một số nguyên duy nhất: phần nguyên của trung bình cộng độ nguy hiểm.

Ràng buộc

• $2\le n\le 2000$
• $1\le k\le n-1$
• $-1\le c_{i,j}\le {10}^9$
• Dữ liệu đảm bảo đồ thị thỏa tính chất nêu trên và đáp án nằm trong kiểu số nguyên 64-bit có dấu.

Ví dụ