Proteins

Magnus is a biologist. He works with proteins all day and wants to know what these molecules look like. He has heard that X-ray crystallography can produce images of proteins that contain many sulfur atoms. Magnus does not think his proteins contain enough sulfur, but he is willing to change them to make this work. Bacteria produce the proteins for him, and he plans to mutate those bacteria to change the proteins.

Magnus knows the DNA string that codes for a protein and how the DNA is translated into an amino acid sequence. The first three letters of the code determine the first amino acid, the next three letters determine the second one, and so on. Whenever those three letters are ATG, in that order, the amino acid methionine goes into the protein. Methionine contains a sulfur atom, so Magnus wants many methionines in his proteins.

The only change Magnus can make to the DNA code is inserting letters. Each inserted letter is A, T, G, or C, and it can go at any position of the string. Inserting one letter takes him a very long time, so he wants to insert as few letters as possible. Find the smallest number of letters he has to insert so that the code produces at least $n$ methionines.

Read the finished string three letters at a time from the beginning. Call each group of three letters a block. Letters left at the end that do not fill a group of three form no block. A block equal to ATG produces one methionine.

For example, TGATGC produces no methionine, but inserting an A at the front turns it into ATGATGC, whose first two blocks are both ATG, so it produces two methionines.

The first line contains the number of methionines $n$ that the protein has to contain. ($1 \le n \le 10^6$)

The second line contains the DNA string. Its length is between 1 and 1000, and each letter is A, T, G, or C.

Print on one line the smallest number of letters that can be inserted into the DNA string so that at least $n$ of its three letter blocks are ATG.