Khi chơi với xâu, bé Thu bắt gặp bài toán sau

• Cho \(n\) xâu \(s_1, s_2, ..., s_n\) chỉ gồm các ký tự in thường từ a đến z. Cần tìm \(m\) lớn nhất sao cho tồn tại các chỉ số \(1 \leq i_1 < i_2 < ... < i_m \leq n\) thỏa \(s_{i_1} < s_{i_2} < ... < s_{i_m}.\)

Kí hiệu \(|S|\) là độ dài xâu \(S\)

Xâu \(a\) được gọi là bé hơn \(b\) (kí hiệu \(a < b\)) nếu \(a\) là một tiền tố của \(b\) (\(|a| < |b|,\) với mọi \(i\) thỏa \(1 \leq i \leq |a|\) thì \(a[i] = b[i]\)) hoặc tại vị trí \(i\) đầu tiên mà \(a[i] \neq b[i]\) thì \(a[i] < b[i]\)

Vì tổng độ dài của \(n\) xâu có thể rất lớn nên để tận dụng độ tương đồng của các xâu, các xâu nhập vào sẽ được chia thành \(k\) block khác nhau, mỗi block có dạng như sau:

• Dòng đầu chứa xâu \(S\) là tiền tố của các xâu trong block và \(t\) là số xâu trong block.
• \(t\) dòng tiếp theo, mỗi dòng chứa xâu \(S'.\) Khi đó xâu nhập vào là \(S + S'.\) Xem giải thích để hiểu rõ hơn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n \leq 10^5\)) là số xâu và \(k\) (\(k \leq n\)) là số block.
• \(k\) block tiếp theo, dòng đầu mỗi block chứa xâu \(S\) và số nguyên dương \(t.\) \(t\) dòng tiếp theo trong mỗi block, mỗi dòng chứa xâu \(S'\)

Dữ liệu đảm bảo tổng độ dài các xâu \(S\) và \(S'\) không vượt quá \(10^6\) và tổng các \(t\) bằng \(n.\)

Output

• In ra \(m\) là số lượng xâu lớn nhất

Example

7 3
aa 2
bb
cc
abc 3
bca
acc
bbb
bb 2
ac
aa

5

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 300, |s_1| + |s_2| + ... + |s_n| \leq 2000.\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.