Một xưởng sản xuất có các công việc lặp đi lặp lại, mỗi công việc được ký hiệu bằng một chữ cái in hoa. Công việc giống nhau cần phải cách nhau ít nhất K đơn vị thời gian mới được thực hiện lại (ví dụ máy móc cần thời gian vệ sinh, thiết lập lại). Trong mỗi đơn vị thời gian, xưởng có thể thực hiện một công việc hoặc để máy nghỉ (idle).

Hãy tìm thời gian tối thiểu để hoàn thành tất cả các công việc.

Đầu vào

• Dòng đầu chứa số nguyên K (0 ≤ K ≤ 100).
• Dòng hai chứa xâu S chỉ gồm chữ in hoa (1 ≤ |S| ≤ 10^4) — ký tự thứ i là loại công việc thứ i.

Đầu ra

Một số nguyên là thời gian tối thiểu.

Ví dụ

Input:
2
AAABBB

Output:
8