Optimal Strategy in Rock-Paper-Scissors Game

In this problem, Li Bai is playing Rock-Paper-Scissors against Gao Shi over \(m\) rounds. Gao Shi has prepared \(n\) possible move sequences (each of length \(m\)), where the \(i\)th sequence is comprised of the moves rock, paper, or scissors. Gao Shi will choose the \(i\)th sequence with probability \(p_i\). Before the game starts, Li Bai can commit to his own sequence of \(m\) moves but must choose it in advance (i.e. he cannot adapt his move based on Gao Shi's choice).

The outcome of each round is determined by the usual rules:

• \(\text{rock}\) beats \(\text{scissors}\),
• \(\text{scissors}\) beats \(\text{paper}\),
• \(\text{paper}\) beats \(\text{rock}\).

For each round, if Li Bai wins, he gains a score of +1; if he loses, he gets -1; and if it is a tie, the score is 0. Li Bai is declared the winner for a given sequence chosen by Gao Shi if his total score \(\left(=\sum_{j=1}^{m}\text{score}_j\right)\) is nonnegative (i.e. wins \(\ge\) losses).

Your task is to help Li Bai determine the maximum possible probability of winning (i.e. the sum of probabilities \(p_i\) for which his pre-committed strategy ensures a nonnegative total score), assuming he chooses his moves optimally.

inputFormat

The input begins with a line containing two integers \(m\) and \(n\) (the number of rounds and the number of Gao Shi's possible strategies, respectively).

The second line contains \(n\) real numbers \(p_1, p_2, \ldots, p_n\) representing the probabilities for each strategy. It is guaranteed that \(\sum_{i=1}^n p_i = 1\).

Each of the next \(n\) lines contains \(m\) strings, each being either rock, paper, or scissors, which describes one of Gao Shi's move sequences.

outputFormat

Output a single real number representing the maximum winning probability that Li Bai can achieve by preselecting an optimal move sequence. Answers within an absolute or relative error of \(10^{-6}\) will be accepted.

sample

1 3
0.5 0.3 0.2
rock
paper
scissors

0.8