Cho một xâu \(S\). Tìm xâu dài nhất xuất hiện ít nhất \(k\) lần trong \(S\).

Dữ liệu vào

• Dòng đầu tiên gồm xâu \(S\)
• Dòng thứ hai gồm số nguyên \(k\)

Dữ liệu ra

• In ra độ dài xâu dài nhất xuất hiện ít nhất \(k\) lần trong \(S\)

Ràng buộc

• \(1 \le k \le |S| \le 10^5\)

Input 1

aababbb
2

Output 1

2

Giải thích

Xâu \(ab\) xuất hiện ít nhất \(2\) lần