Turtle Matching Game

This problem is about simulating a popular live-streaming blind box game called "Turtle Matching". In the game, a streamer arranges a sequence of blind boxes, each containing a resin turtle of one of 10 colors (represented by digits 0–9). A consumer (player) first purchases a number of boxes and then additional boxes are gifted during the game depending on the configuration of the turtles in a 3×3 grid.

The game process is divided into three phases in each round:

• Phase 1 (Grid Reveal and Check): From the available unopened blind boxes (initially the purchased ones and later any gifted ones), the consumer takes boxes in order and places the turtles into a 3×3 grid (cells numbered 1 to 9 in row‐major order). Then, the following conditions are checked in order:
  • Condition 3: If the grid is full (all 9 cells are occupied) and all turtles are of distinct colors, then all 9 turtles are removed from the grid. The consumer collects these turtles and 10 additional blind boxes are gifted. (Note: when Condition 3 applies, no extra bonus from Condition 2 is granted.)
  • Condition 1: Otherwise, if there exists any color that appears at least twice (the pair need not be adjacent), then for each color you remove as many turtles as possible in pairs. For a color appearing n times, exactly 2×⌊n/2⌋ turtles are removed. The consumer collects all removed turtles and for each pair removed, 1 blind box is gifted.
  • Condition 2: After performing the removals for Condition 1, if the grid becomes empty (i.e. no turtle remains), then an additional 8 blind boxes are gifted.
  If none of the above conditions is satisfied, then all turtles in the grid (which might be less than 9 if the grid is not completely filled) are removed and given to the consumer, and the matching phase ends immediately.
• Phase 2 (Gifting): The gifted blind boxes are appended to the end of the remaining unopened blind boxes. These gifted boxes are taken sequentially from the blind box sequence.
• Phase 3 (Refill): The empty cells in the grid are refilled with the next unopened boxes (in the original order, filling cells in increasing order of their index). Then the process repeats from Phase 1.

The consumer’s final collection of turtles is the sum of the turtles from the originally purchased blind boxes and all the turtles obtained via the matching (gifting) process.

Formally, you are given a string S of length n representing the sequence of blind boxes, where S[i] (1-indexed) indicates the color of the turtle in that box. The consumer purchases the first a boxes (i.e. S[1] to S[a]). The remaining boxes (from S[a+1] onward) are used as the source for gifted boxes. Simulate the game and determine how many turtles the consumer collects by the end.

Notes:

• For any number n, the notation \(\lfloor n/2 \rfloor\) denotes the floor of n/2.
• Assume that the blind box sequence is long enough to cover all gifting events during the game.

inputFormat

The input consists of two lines.

• The first line contains an integer a (\(1 \le a \le n\)), which is the number of blind boxes purchased by the consumer.
• The second line contains a string S of length n (\(n \ge a\)), consisting of digits from 0 to 9. Each digit represents the color of the turtle in that box. The first a characters represent the purchased boxes and the remaining characters are used for gifting.

outputFormat

Output a single integer—the total number of turtles the consumer collects by the end of the game.

sample

9
1123456789

10