题目描述

Ertanis 一直谋划着送给 XXX 很多很多糖果。

经过了很久的准备后，Ertanis 共买好了 $k$ 种不同口味的糖果，共计 $n$ 包，每包均有 $10^s$ 颗糖果，且这 $n$ 包现在杂乱的在桌面上排成一排。由于种种奇葩原因，Ertanis 每次只会选择连在一起的同种糖果送给 XXX， 而 XXX 则会一颗一颗很快把得到的糖果吃完。不幸的是，由于量子理论的扰动，对于第 $i$ 种糖果的每一颗均有 $c_i$ 的概率不好吃。但糖果本身还是很对 XXX 胃口的，若 XXX 在吃到难吃糖果或吃完了 Ertanis 这次送的所有糖果时已连续吃了 $k$ 颗好的第 $i$ 种糖果，可得到 $k^{p_i}$ 的快乐指数。

自然，Ertanis 希望糖果给 XXX 带来的快乐指数越大越好，但他是一个蒟蒻，对此完全没有一点头绪，就只好请你帮他算出采用最优方案时糖果所能带来的快乐指数的期望值。算完后 Ertanis 会给你 $100$ 颗 $c_i=1$ 的糖果作为奖励。

输入格式

第一行两个整数 $n$ 和 $k$，表示糖果总数和口味数。

第二行n个整数 $g_i$，表示第 $i$ 颗糖的口味。

第 $3$ 到 $k+2$ 行，每行先给出一个整数 $p_i$，然后是一个实数 $c_i$，含义如描述中所示。

输出格式

一个实数，表示 Ertanis 采用最优方案时快乐指数的期望值，保留至小数点后 $3$ 位。

3 2 0
1 2 1
2 0.5
1 0.4

2.100

5 2 0
1 2 1 2 1
4 0.5
2 0

16.750

数据规模与约定

对于 $30\%$ 的数据，保证 $k=1$。

对于另外 $40\%$ 的数据，保证对任意 $c_i ~(1 \le i \le k)$ 存在 $c_i = 0$ 或 $c_i=1$。

对于 $100\%$ 的数据，保证 $1 \le n \le 200$，$1 \le k \le \max(n,15)$，$1 \le g_i \le k$，$1 \le p_i \le 4$，$0 \le s \le 2$，数据中所有实数小数部分不超过 $2$ 位，保证任意糖果总数量均不大于 $5 \times 10^4$，保证答案不大于 $10^{15}$，不保证每种糖果都出现。