Xoắn là một cậu bé rất thích những bài tập về chuỗi, cậu cảm thấy thoải mái khi loại bỏ những kí tự ở đầu chuỗi, hoặc cuối chuỗi, nhưng lại rất ghét khi phải loại bỏ các kí tự ở giữa chuỗi, tức là những kí tự không phải ở đầu hoặc cuối chuỗi.

Một hôm Trâu có cho cậu một chuỗi toàn kí tự 'D', 'H' và 'A', Trâu đố Xoắn tìm được chuỗi con ngắn nhất của chuỗi vừa cho, sao cho chuỗi con đó có ít nhất k kí tự 'D', k kí tự 'H' và k kí tự 'A . Xoắn thừa sức làm bài ez như vậy, xoắn thêm yêu cầu cho bản thân là chuỗi con đó có thể chuyển thành chuỗi có đúng k kí tự 'D', k kí tự 'H' và k kí tự 'A' bằng cách chỉ sử dụng ba loại thao tác xóa kí tự ở đầu/cuối/giữa chuỗi và số lần phải xóa kí tự ở giữa là ít nhất.

X là chuỗi con của Y là một chuỗi gồm các kí tự liên tiếp của Y

Input

Dòng đầu tiên chứa số k ~(1 \le k \le n/3) ~.

Dòng thứ 2 chuỗi s chỉ gồm các kí tự thuộc tập {'D', 'H', 'A'} có độ dài là n ~(1 \le n \le 2.10^5 )~

Output

In ra số lần phải xóa kí tự ở giữa, nếu k có chuỗi con nào thỏa mãn in ra -1.

Sample Input 1

2
DHHDHADHHAAAHD

Sample Output 1

1

Giải thích IN/OUTPUT 1 :

Chuỗi con Xoắn sẽ tìm được là "DHADHHA" chỉ phải loại thực hiện 1 thao tác xóa ở giữa là tại vị trí 2 thành chuỗi "DADHHA" có đúng 2 kí tự 'D', 2 kí tự 'H' và 2 kí tự 'A'