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ẽ):

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.