P12228 「WyOJ Round 1」持 · 山海为肩

>人生得意须尽欢，莫使金樽空对月。天生我材必有用，千金散尽还复来。 > >—— 李白《将进酒》

李白和高适在玩石头剪刀布，总共有 $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

对于 $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$ 位。 | 测试点 | 数据范围 | | -----------: | ----------- | | $1\sim 3$ | $1\le n\le 10^3$，$1\le m\le 5$ | | $4\sim 10$ | $1\le n\le 10^5$，$1\le m \le 12$ |