KiKoS là một người hâm mộ bộ phim truyền hình "How I Met Your Mother". Gần đây, anh ấy đã khám phá ra một danh sách phát trên Spotify chứa nhạc phim của bộ phim này.
Bên cạnh những bản hit không thể phủ nhận như "Let's Go to the Mall" và "Nothing Suits Me Like a Suit", anh ấy tìm thấy một bài hát rất ngớ ngẩn: "Bang bang bangity bang". Về cơ bản, đây là cụm từ duy nhất trong toàn bộ bài hát. Để làm cho bài hát dài hơn, bạn chỉ cần nói lại chính câu đó nhưng thêm "I said" vào đầu câu, rồi lại có thể hát lại toàn bộ từ đầu.
Là một nhạc sĩ mới vào nghề, KiKoS muốn tái sử dụng cấu trúc này cho một bài hát mới. Một cách hình thức, với một từ khác rỗng $\mathbb{S}$ gồm các chữ cái tiếng Anh viết thường, bài hát $\mathbb{S}$ được tạo thành từ một khối gồm hai dòng có thể được lặp lại nhiều lần với cùng một từ $\mathbb{S}$ đó. Mỗi khối có dạng như sau:
$$ \begin{aligned} &\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \\ &\texttt{i said }\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \end{aligned} $$
Cho một văn bản lớn gồm nhiều dòng, hãy xác định số lượng ký tự tối đa có thể có trong một dãy các khối liên tiếp tạo thành một bài hát hợp lệ.
Dữ liệu vào
Dữ liệu vào gồm nhiều dòng, chỉ chứa các chữ cái tiếng Anh viết thường, dấu phẩy và dấu cách. Mỗi dòng kết thúc bằng một ký tự xuống dòng. Tổng số lượng ký tự bao gồm cả các ký tự xuống dòng không vượt quá $10^5$.
Không có dòng trống, và các dòng không bắt đầu hay kết thúc bằng dấu cách.
Dữ liệu ra
In ra một số nguyên duy nhất: số lượng ký tự tối đa có thể có trong một dãy các khối liên tiếp khớp với mẫu bài hát. Số lượng này bao gồm cả các ký tự xuống dòng ở cuối mỗi dòng của dãy, kể cả dòng cuối cùng của bài hát. Mỗi ký tự xuống dòng được tính là $1$ ký tự: hãy chú ý điều này nếu bạn sử dụng môi trường Windows.
Nếu không có khối nào khớp với mẫu bài hát, hãy in ra $-1$.
Ví dụ
Dữ liệu vào 1
bang, bang bangity bang i said bang, bang bangity bang
Dữ liệu ra 1
55
Dữ liệu vào 2
bang, bang bangity bang i said bang, bang bangity bang bank, bank bankity bank i said bank, bank bankity bank bank, bank bankity bank i said bank, bank bankity bank
Dữ liệu ra 2
110
Dữ liệu vào 3
grandmasters are red, experts are blue, parsing problems are bad, but we believe in you
Dữ liệu ra 3
-1