“We Cut The Cheese” 特色食品店销售各种特制的奶酪混合产品。例如，他们的“意大利混合”由 50% 的波萝伏洛干酪、30% 的马苏里拉干酪和 20% 的帕尔马干酪组成，而他们的“非洲狩猎”则由 74% 的多米亚蒂干酪、25% 的阿里什干酪和少许（1%）的博克马基里干酪组成。你最初在店里担任奶酪混合品鉴师，但两年后，你凭借自己的努力升任会计办公室主管。每周，商店都会根据季节、市场价格和其他因素收到各种奶酪的货运。给定这些数量以及每种奶酪混合产品所需的百分比，你需要每周确定这些奶酪的最佳使用方案，以实现利润最大化。当商店只制作几种不同的奶酪混合产品时，这还可以手工完成，但随着业务的扩张速度超过了奶酪舒芙蕾的膨胀速度，混合产品的数量也增加到了需要编写程序来确定奶酪货运最佳使用方案的地步。所以问题是：你是否有足够的“奶酪（gouda-nough）”水平来编写这样一个程序？

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$ ($1 \le n, m \le 50$)，其中 $n$ 是用于制作奶酪混合产品的奶酪种类数，$m$ 是商店提供的不同奶酪混合产品的数量。下一行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 500$)，其中 $w_i$ 是商店现有的第 $i$ 种奶酪的磅数。接下来的 $m$ 行，每行包含 $p_1, p_2, p_3, \dots, p_n, t$ ($0.0 \le p_i \le 100.0, 0.0 \le t \le 10.0$)，其中 $p_i$ 表示混合产品中第 $i$ 种奶酪的百分比，$t$ 是该混合产品的每磅利润。

输出格式

输出在给定奶酪磅数、混合百分比和利润的情况下，假设所有混合奶酪都能售出时所能获得的最大利润。将结果四舍五入到最接近的便士（即保留两位小数）。

样例

样例输入 1

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 50.0 50.0 2.80

样例输出 1

920.00

样例输入 2

3 2
100 150 100
50.0 50.0 0.0 3.20
0.0 40.0 60.0 2.80

样例输出 2

1000.00