Quy hoạch thành phố

Thành phố \(A\) đang quy hoạch xây dựng đô thị kiểu mẫu với các tiêu chuẩn "xanh, sạch, đẹp, hiện đại", trong đó có dự án sơn các ngôi nhà liền kề trên cùng một trục đường để có màu sắc giống nhau, với chi phí cho phép là \(k\).

Hiện tại mỗi ngôi nhà được sơn với một màu và mỗi màu được biểu diễn bằng một kí tự từ 'a' đến 'z'. Chi phí chuyển đổi màu sơn của ngôi nhà từ màu \(x\) sang màu \(y\) là khoảng cách từ vị trí kí tự biểu diễn màu sơn \(x\) đến vị trí kí tự biểu diễn màu sơn \(y\) trong bảng mã ASCII.

Ví dụ, chi phí chuyển đổi từ màu biểu diễn bằng kí tự 'a' sang màu biểu diễn bằng kí tự 'b' là \(|97 - 98| = 1\).

Yêu cầu. Hãy xác định số lượng lớn nhất các ngôi nhà liên tiếp có thể được sơn cùng màu sau khi thực hiện các phép đổi màu với tổng chi phí không vượt quá \(k\).

Input

• Dòng đầu tiên chứa số nguyên dương \(k\) (\(k \le 10^5\)).
• Dòng thứ hai chứa xâu \(S\) (\(|S| \le 5 \cdot 10^5\)), là xâu biểu diễn màu sơn hiện tại của các ngôi nhà.

Output

Ghi ra một số nguyên duy nhất là kết quả cần tìm.

Input

%
2
babac

Output

%
4

Input

%
2
afab

Output

%
2

Notes

Ở ví dụ thứ nhất, có thể đổi 'b' thành 'a' hoặc đổi 'a' thành 'b' để thu được một đoạn liên tiếp dài \(4\) có cùng màu.

Scoring

• (60%) \(|S| \le 10^3\).
• (40%) \(|S| \le 5 \cdot 10^5\).