Bài 30: Quy hoạch thành phố

Yêu cầu: Thành phố A đang quy hoạch 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~. Mỗi ngôi nhà được sơn một màu biểu diễn bằng một kí tự từ 'a' đến 'z'. Chi phí chuyển đổi từ màu ~x~ sang màu ~y~ là khoảng cách giữa 2 kí tự trong bảng mã ASCII (ví dụ: |'a' - 'b'| = |97 - 98| = 1). Hãy tìm số lượng nhiều nhất các ngôi nhà liền kề có cùng màu sơn sau khi thực hiện dự án, với tổng chi phí không vượt quá ~k~.

Giới hạn:

• ~1 \le k \le 10^5~
• ~1 \le |S| \le 5 \times 10^5~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (PLAN.INP):

• Dòng đầu tiên ghi số nguyên dương ~k~.
• Dòng thứ hai ghi xâu ~S~ biểu diễn màu sơn hiện tại.

Kết quả (PLAN.OUT):

• Ghi ra một số nguyên duy nhất là chiều dài đoạn nhà dài nhất.

Ví dụ:

Input:

2
babac

Output:

4

(Giải thích: Chuyển 'b' -> 'a' (chi phí 1). Xâu thành 'aaaac' (tổng chi phí là 2). Có 4 nhà liền kề màu 'a').