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 sơn đượ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 sơn ~x~ sang màu sơn ~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 sơn biểu diễn bằng ký tự 'a' sang màu sơn biểu diễn bằng ký tự 'b' là ~|97 - 98| = 1~.

Hãy viết chương trình giúp ban quản lý quy hoạch đô thị giải quyết dự án trên.

Yêu cầu: Đưa ra số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn sau khi thực hiện dự án, với tổng chi phí chuyển đổi không vượt quá ~k~.

Input

• Dòng đầu tiên ghi số nguyên dương ~k~ (~k \le 10^5~) là chi phí cho phép của dự án;
• Dòng thứ hai ghi xâu ký tự ~S~ có độ dài xâu ~|S| \le 5 \times 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 dòng duy nhất là kết quả cần tìm.

Sample Input 1

2
babac

Sample Output 1

4

Giải thích: Ta thực hiện biến đổi ký tự 'b' -> 'a' (hoặc 'a' -> 'b') và thu được xâu mới 'aaaac' (hoặc 'bbbbc'). Tổng chi phí biến đổi là 2. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là 4.

Sample Input 2

2
afab

Sample Output 2

2

Giải thích: Ta thực hiện biến đổi ký tự 'b' -> 'a' (hoặc 'a' -> 'b') và thu được xâu mới 'afaa' (hoặc 'afbb'). Tổng chi phí biến đổi là 1. Số lượng nhiều nhất các ngôi nhà liền kề cùng màu sơn là 2.

Giới hạn

• 60% số test có độ dài xâu ~|S| \le 10^3~;
• 40% số test có độ dài xâu ~|S| \le 5 \times 10^5~.