ami lại cho các bạn một xâu kí tự \(S\) gồm \(N\) chữ cái tiếng Anh in thường và một số nguyên dương \(k\). Các bạn có thể áp dụng thao tác sau không quá \(k\) lần:

• Chọn ra một số \(i\) với \(0 \leq i \lt N\) và đổi \(S_i\) thành một kí tự bất kì.

Đặt \(F(S)\) là độ dài đoạn con dài nhất của \(S\) chỉ chứa các kí tự giống nhau.

Hãy áp dụng thao tác trên một cách tối ưu để \(F(S)\) là lớn nhất và in ra giá trị này.

Input

• Dòng đầu tiên chứa 1 xâu kí tự \(S\).

• Dòng tiếp thao chứa một số nguyên dương \(k\).

Output

• Một số nguyên dương là \(F(S)\) lớn nhất sau khi thực hiện thao tác không quá \(k\) lần.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(1\) \(\leq\) \(k\) , \(N\) \(\leq\) \(100\).
• Subtask \(2\) (\(40\%\) số điểm): \(1\) \(\leq\) \(k\) , \(N\) \(\leq\) \(10^5\).

Example

cuomquaga
1 

3