Một công ty có \(n\) nhân viên đang chuẩn bị tái cơ cấu. Cơ cấu tổ chức mới được biểu diễn bằng một cây có gốc, trong đó mỗi đỉnh là cấp trên trực tiếp của các đỉnh con của mình.

Mỗi nhân viên có một danh sách những người mà họ chấp nhận làm cấp trên. Ngoài ra, tất cả nhân viên đều phải được trả lương. Mức lương phải là một số nguyên dương, và lương của mỗi cấp trên phải lớn hơn tổng lương của các cấp dưới trực tiếp của người đó.

Nhiệm vụ của bạn là tổ chức lại công ty sao cho tất cả các điều kiện trên đều được thỏa mãn và tổng lương của toàn bộ nhân viên nhỏ nhất có thể.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(n\): số nhân viên. Các nhân viên được đánh số \(1,2,\ldots,n\).

\(n\) dòng tiếp theo mô tả nguyện vọng của các nhân viên. Dòng thứ \(i\) trong số này chứa số nguyên \(k_i\), theo sau là danh sách gồm \(k_i\) số nguyên. Danh sách này gồm tất cả những nhân viên mà nhân viên thứ \(i\) chấp nhận làm cấp trên của mình.

Dữ liệu ra

In ra tổng lương nhỏ nhất trong tất cả các cách tái cơ cấu hợp lệ. Dữ liệu bảo đảm tồn tại ít nhất một cách thỏa mãn.

Phân nhóm

1. Nhóm 1 (22 điểm): \(2 \le n \le 10\); \(\sum_{i=1}^{n} k_i \le 20\).
2. Nhóm 2 (45 điểm): \(2 \le n \le 100\); \(\sum_{i=1}^{n} k_i \le 200\).
3. Nhóm 3 (33 điểm): \(2 \le n \le 5000\); \(\sum_{i=1}^{n} k_i \le 10000\).

Ví dụ

4
1 4
3 1 3 4
2 1 2
1 3

8

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ nhất, bài A.