Practice Strings and Geometry with the exercise "String balls"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

Note: You can find the second part of this puzzle, made by @Timinator, at:

https://www.codingame.com/training/hard/string-balls-ii

Statement:
Let's name the string abcdefghijklmnopqrstuvwxyz the alphabet, and let d be the distance between two elements in the alphabet defined by the absolute value of the difference of their indexes. For example:

  
  d("b", "d") = d("d", "b") = 2
  d("f", "f") = 0
  d("a", "z") = 25

We can extend d to strings of equal length as follows: given two strings sa, sb of equal length len, d(sa, sb) is the sum of the pairwise d(sa[i], sb[i]) for all index values (i) from 0 to len-1. For example:


  d("fb", "fd") = d("f", "f") + d("b", "d") = 0 + 2 = 2
  d("ab", "ac") = d("ac", "ab") = 1
  d("ac", "bb") = 2

We can now define a (closed) ball of center a given string and of (integer) radius. A point p (i.e. a string with letters in the alphabet and of same length as the center) is inside the ball if d(center, p) <= radius.

Find the number of points contained in the ball of center center and radius radius.

Example (Test 4):
2
ab

The points at distance less or equal to 2 of ab are:
- at distance 0: ab
- at distance 1: bb, aa, ac
- at distance 2: cb, ad, bc, ba

For a total of 8 points contained in the (closed) ball of center ab and radius 2.

NB: Tests 1-7 cover simple cases and should help you debug your program. Tests 8-11 check the performance.

Input

Line 1: An integer radius, the radius of the ball.
Line 2: A string center, the center of the ball.

Output

The number of points inside the ball of center center and radius radius.

Constraints

0 < radius <= 100
0 < length(center) < 20
0 <= answer <= 1e6
The string center contains only lowercase English letters.

Example

Input

1
a

Output

Solve it

A higher resolution is required to access the IDE