题目背景

人生得意须尽欢，莫使金樽空对月。天生我材必有用，千金散尽还复来。

—— 李白《将进酒》

题目描述

李白和高适在玩石头剪刀布，总共有 $m$ 轮。

李白是天赋型选手，提前预知了高适可能的出招方式和概率。具体而言，高适有 $n$ 种出招方式，第 $i$ 种方式是由 rock，paper，scissors 构成的长度为 $m$ 的序列，出招使用第 $i$ 种方式的概率为 $p_i$。

李白想知道，在最优策略下，获胜的概率最大是多少？获胜指李白赢的轮数不小于输的轮数。

注意：paper 能击败 rock，scissors 能击败 paper，rock 能击败 scissors 。

注意：李白的策略是不能根据高适出的东西来决定。李白的 $m$ 次出法必须在开始就全部定下来。

输入格式

第一行包含两个整数 $n$ 和 $m$，表示出招方式的数量和比赛的轮数。

接下来 $n$ 行，每行先输入一个浮点数 $p_i$，然后是 $m$ 个由 rock，paper，scissors 构成的元素。

输出格式

第一行一个浮点数，表示最大的概率，四舍五入保留 $6$ 位小数。

第二行，输出能得到最大概率的字典序最小的方案。

注：方案 $p$ 比方案 $q$ 字典序小，当且仅当存在位置 $i$ 使得：

• $\forall j\in [1,i), p_j=q_j$ 且 $p_i<q_i$。这里 $p_i$ 和 $q_i$ 分别表示两个方案在第 $i$ 轮出的是 rock，paper 还是 scissors，特别注意，字典序上从小到大的顺序为 rock，paper，scissors。

2 3
0.3 rock scissors paper
0.7 rock rock scissors

1.000000
rock rock rock

提示

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 12$。保证 $p_i\in [0,1]$ 且 $\sum\limits_{i=1}^n p_i=1$。$p_i$ 小数点后至多 $6$ 位。