DNA là thành phần cơ bản cấu tạo thành bộ genome của sinh vật. DNA bao gồm 4 loại khác nhau là {A,X,T,G}. Để nghiên cứu các sinh vật ở mức độ phân tử, người ta tiến hành giải mã bộ genome của chúng.

Để giải mã bộ genome của một sinh vật, máy giải mã thế hệ mới sẽ sinh ra N đoạn cơ sở, mỗi đoạn cơ sở là một dãy bao gồm 30 DNA. Các đoạn cơ sở sẽ được ghép nối với nhau để tạo thành một bộ genome hoàn chỉnh.

Ta nói một đoạn DNA X được bao phủ bởi một đoạn cơ sở Y nếu tồn tại một đoạn của Y trùng với X. Giả sử k là một số nguyên dương, một đoạn DNA X được gọi là đoạn tin tưởng cấp k nếu X được bao phủ bởi ít nhất kđoạn cơ sở.

Yêu cầu: Cho n đoạn cơ sở và số nguyên dương k, hãy tìm đoạn tin tưởng cấp k có độ dài lớn nhất.

Dữ liệu: 

- Dòng đầu chứa hai số nguyên dương n và k (0< k ≤ n ≤ 30.000);

- Trong n dòng tiếp theo, mỗi dòng chứa một đoạn cơ sở.

Kết quả: Ghi  một số nguyên xác định độ dài của đoạn tin tưởng tìm được (ghi -1 nếu không tồn tại đoạn tin tưởng cấp k).

Ví dụ: