Có ~n~ phép biến đổi từ ~n~ số tự nhiên ~1,2,3,..,n~. Phép biến đổi thứ ~i (i = 1,2,3,..,n)~ biến đổi số ~i~ thành tập các số nguyên ~{i_1,i_2,..,i_k}~ trong đó ~1 ≤ i_1,i_2,..,i_k≤n~. Ta kí hiệu tập này là ~Set(i)~. Chú ý là tập ~Set(i)~ có thể có các số bằng nhau.
Bạn được phép thực hiện ~S~ lần biến đổi.
- Lần 1, chọn một số ~i~ và biến đổi thành ~Set(i)~, tập các số nhận được kí hiệu là ~A = Set(i)~.
- Lần 2, chọn một số ~u~ thuộc tập ~A~ và biến đổi ~u~ thành ~Set(u)~, khi đó tập các số nhận được ~A~ gồm các số từ tập ~A~ cũ và các số từ tập ~Set(u)~ và bỏ đi số ~u~ được biến đổi.
- Lần 3, 4, .., ~S~ được thực hiện tương tự như lần 2.
Ví dụ: ~n~ = 3;
- Phép biến đổi 1: (1) → (2, 2, 3)
- Phép biến đổi 2: (2) → (1, 3)
- Phép biến đổi 3: (3) → (2, 3)
Ta có 1 trường hợp về biến đổi khi thực hiện biến đổi 3 lần (hình vẽ):
![](http://oj.lequydon.net/media/martor/4f7c1d2d-bd5a-4906-9977-ec2ab4eb447f.png)
Như vậy từ số 2, sau khi thực hiện 3 lần biến đổi, ta thu được tập ~A~ gồm 5 số ~(3, 2, 2, 2, 3)~.
Yêu cầu: Hãy tìm cách chọn một số ~i (i = 1,2,..,n)~, bắt đầu từ số ~i~ đã chọn, hãy tìm cách thực hiện ~S~ lần biến đổi để thu được tập ~A~ cuối cùng gồm nhiều số hạng nhất.
Dữ liệu gồm:
- Dòng đầu ghi số nguyên dương ~n~.
- Dòng thứ ~i~ trong ~n~ dòng tiếp theo, mỗi dòng có dạng: Số đầu là ~k~, tiếp theo là ~k~ số ~i_1,i_2,..,i_k~ mô tả phép biến đổi thứ ~i~, biến ~(i) → (i_1,i_2,..,i_k)~.
- Dòng cuối ghi số nguyên dương ~S~.
Kết quả
- Số các số hạng của tập ~A~ gồm nhiều số hạng nhất có thể biến đổi được.
Ví dụ
Input
3
3 2 2 3
2 1 3
2 2 3
3
Output
6
Giải thích
Cách biến đổi tối ưu: (1) → (2, 2, 3) → (1, 3, 2, 3) → (2, 2, 3, 3, 2, 3).
Giới hạn:
- Trong mọi test, ~k ≤30; n ≤1000; S ≤50~;
- Có 25% số test ứng với ~S = 2~;
- Có 25% số test ứng với ~S = 3~;
- Có 50% số test còn lại không ràng buộc gì thêm.
Comments
Đã có nội dung!