Ta định nghĩa giá trị của một xâu T độ dài k là value(T) được tính bằng số cặp (i, j)(1 ≤ i < j ≤ k) sao cho Ti = a và Tj = b . Cho xâu S gồm toàn chữ cái Latin in thường độ dài N và một số nguyên C. Bạn hãy tìm một giá trị X lớn nhất có thể sao cho tồn tại một xâu con Sx độ dài X của xâu S có value(Sx) ≤ C.

Input

• Dòng đầu tiên chứa hai số nguyên dương N, C (~ 1 ≤ N ≤ 10^6, 0 ≤ C ≤ 10^{18} ~).

• Dòng thứ hai chứa xâu S độ dài N.

Output

• Một số nguyên duy nhất là kết quả bài toán.

Sample

Input #1

6 2
aabcbb

Output #1

4

Problem source: Free Contest Cup 2018