8358번 - Safe 다국어

Byteman keeps all of his savings in an old safe. The lock of this safe consists of n identical wheels, each of them has the same word consisting of m letters written on it. Wheels can be rotated independently of each other (this way each wheel can be put in m different positions). Safe gets opened, when for all m positions letters written on all wheels for that position are the same.

Recently one of the Byteman's acquaintance told him that it is a good idea to keep money in a bank. Byteman decided to open his safe as soon as possible and transfer all of his money to a high-interest bank account. Assuming that rotation of any wheel by 360/m degrees to the left or to the right can be performed within one second, calculate, how long would it take (at minimum) to open Byteman's safe.

Help Byteman!

The first line of the standard input contains two integers n and m (2 ≤ n, m ≤ 1 000 000), separated with a single space and denoting the number of wheels in the lock and the length of the word written on each wheel. The second line of the input contains one word s₁s₂...s_m of length m, consisting of large English letters. In the third line there are n integers o₁, o₂, ..., o_n (0 ≤ o_i < m), separated with single spaces. o_i = k means that the word from the i'th wheel is rotated by k positions to the left (relatively to some defined initial position), which means it is set in position s_k+1s_k+2...s_ms₁s₂...s_k. For instance, if o_i = 0 then the word on the i'th wheel is not rotated at all.

The first and only line of the standard output should contain one integer, the minimal time required to open Byteman's safe.

For the example lock, words written on each wheel look as follows:

OWIKSL
SLOWIK
WIKSLO
KSLOWI

For example, rotating the first wheel by one position to the left gives WIKSLO. When we rotate the same wheel to the right instead, we get LOWIKS.