Cho xâu ~S~ biểu diễn màu hiện tại của các ngôi nhà, mỗi màu là một chữ cái từ a đến z. Chi phí đổi màu ~x~ sang màu ~y~ là ~|x-y|~. Cho giới hạn tổng chi phí ~k~.

Yêu cầu

Tìm độ dài lớn nhất của một đoạn con có thể đổi thành cùng một màu với tổng chi phí không vượt quá ~k~.

Input

Một dòng chứa số nguyên ~k~ và xâu ~S~ ~(0 \le k \le 10^9, |S| \le 5\cdot 10^5)~.

Output

In ra độ dài lớn nhất.

Subtask

• Subtask 1: ~|S| \le 10^3~.
• Subtask 2: ~|S| \le 5\cdot 10^5~.

Ví dụ

3 abcde

3