Resources A/P Conversion Cycles

In each cycle, first consume conversionRate P's to convert them into one A; if that is not possible and there is an A, consume one A; if neither can be done, stop, and the stopping action does not count as a cycle. Follow the statement strictly: consuming an A does not produce any extra P. The original first two examples, 13 and 4, conflict with the statement and are corrected to 5 and 2 respectively.

This site's standard input and output are explicit.

输入格式

The first line contains n conversionRate, and the second line contains a contiguous string of n A/P characters. 2≤n≤500, 2≤conversionRate≤500.

输出格式

Output one integer, the answer.

样例 1

输入：

6 2
AAAPPP

输出：

5

样例 2

输入：

2 2
AA

输出：

2

样例 3

输入：

3 3
PPP

输出：

2

样例说明

Example 1: convert once, leaving 4 A's and 1 P, then consume 4 A's, for 5 cycles in total. Example 2: consume two A's and stop, for 2 cycles in total. Example 3: convert once to get an A, then consume it, for 2 cycles in total.