Roulette Score (APCS 2025-06 Intermediate)

You have \(m\) roulettes. Each roulette contains \(n\) positions, and every position is labeled with one lowercase English letter. Each input string of length \(n\) lists the currently visible letters of one roulette from top to bottom.

The game has \(k\) rounds. In every round, each roulette is rotated by a given integer distance:

• A positive distance \(d\) rotates the roulette clockwise by \(d\) positions, which is a cyclic right shift of its string by \(d\) positions.
• A negative distance \(d\) rotates the roulette counterclockwise by \(-d\) positions, which is a cyclic left shift by \(-d\) positions.
• A distance of 0 leaves the roulette unchanged.

For example, for the length-6 roulette apcsie:

• A clockwise rotation by 1 produces eapcsi.
• A counterclockwise rotation by 2 produces csieap.

A rotation distance may exceed one full turn and must be interpreted cyclically. More importantly, each round starts from the state at the end of the previous round. The roulettes are not reset to their initial strings.

After all roulettes have been rotated in one round, score each position separately. At a position, inspect the \(m\) aligned letters and find the largest number of occurrences of any one letter. This number is the score of that position. The score of the round is the sum of the scores of all \(n\) positions.

Output the sum of the scores over all \(k\) rounds.

Input

The first line contains three positive integers \(m\), \(n\), and \(k\): the number of roulettes, the number of positions on each roulette, and the number of rounds.

Each of the next \(m\) lines contains a string of exactly \(n\) lowercase English letters, describing the initial state of one roulette.

Each of the next \(k\) lines contains \(m\) integers. The \(j\)-th integer on the \(r\)-th such line is the rotation distance of the \(j\)-th roulette in round \(r\).

Constraints

• \(1\le m,n,k\le30\)
• Every roulette string contains exactly \(n\) letters from a to z
• \(-100\le d\le100\) for every rotation distance \(d\)

Output

Output one integer: the total score over all \(k\) rounds.

Scoring

Sample Input 1

3 6 2
apcsie
taiwan
icpeda
1 0 -4
7 -3 2

Sample Output 1

17

Sample Explanation 1

Round 1 starts from the three initial strings:

1. Rotate apcsie clockwise by 1 to obtain eapcsi.
2. Leave taiwan unchanged.
3. Rotate icpeda counterclockwise by 4 to obtain daicpe.

The six positions are scored as follows:

The score of round 1 is \(1+3+2+2+1+1=10\).

Round 2 must continue from the strings at the end of round 1:

1. Rotate eapcsi clockwise by 7. Since \(7\bmod6=1\), it becomes ieapcs.
2. Rotate taiwan counterclockwise by 3 to obtain wantai.
3. Rotate daicpe clockwise by 2 to obtain pedaic.

The score of round 2 is \(1+2+1+1+1+1=7\), so the total is \(10+7=17\).

Sample Input 2

4 3 3
abc
bab
cbc
abc
-1 -6 -6 -7
5 -3 4 0
-7 4 2 8

Sample Output 2

21

Sample Explanation 2

The states and scores after each round are shown below. Every row continues from the state in the previous row.

Therefore, the total score is \(7+7+7=21\).

Source

APCS June 2025, Programming Task 2; ZeroJudge q837, Roulette Score; explanation by Yi-Che Wang.