问题描述

$H$ 市是一座制造业十分发达的城市。在 $H$ 市中，工厂可以生产 $n$ 种不同的物品，部分物品都可以以特定的价格 $a_i$​ 在市场上售出而带来收益。生产方式分为两类，使用第一类生产方式每个工人可以在一天时间内生产若干件物品 $y$。使用第二类生产方式，每个工人可以在一天时间内使用若干件物品 $x$ 生产若干件物品 $y$，其中 $x≤y$，即只能将编号较小的物品加工成编号较大的物品。

小蓝作为 $H$ 市的市长自然希望能够最大化收益，由于 $H$ 市的人口非常多，你只需要帮她计算出平均一天内每个工人能够获得的最大收益即可。

输入格式

输入的第一行包含两个正整数 $n,m$，用一个空格分隔，其中 $n$ 表示物品种数，$m$ 表示生产方式总数。

第二行包含 $n$ 个正整数 $a_i$，相邻整数之间使用一个空格分隔，表示物品的售价，若 $a_i=0$ 则表示这种物品无法在市场上售出。

接下来 $m$ 行，每行包含四个非负整数 $x_i,y_i,k_i,w_i$，相邻整数之间使用一个空格分隔，表示一个工人可以在一天时间内使用 $k_i$​ 件物品 $x_i$​ 生产 $w_i$​ 件物品 $y_i$。特殊地，如果 $k_i=0$（此时 $x_i$​ 不一定为 0 ，请忽略 $x_i$​ 的值）则表示该种生产方式是第一类生产方式，不需要原材料。

输出格式

输出一行包含一个实数，四舍五入保留正好两位小数，表示平均每个工人在一天时间内能够获得的最大收益。

3 3
1 0 2
1 1 0 6
1 2 5 10
2 3 6 10

9.52

样例说明

$1$ 个工人可以在一天时间内生产 6 份小麦，或者将 5 份小麦加工成 10 份面粉，或者将 6 份面粉加工成 10 份饼干。

那么最理想的情况是 $5$ 个工人生产小麦， $6$ 个工人将小麦加工成面粉， $10$ 个工人将面粉加工成饼干后在市场上以 2 的价格出售。

此时需要 $21$ 个工人生产，共能获得 200 的收益平均每个工人一天时间内获得的收益约为 9.52。

评测用例规模与约定

对于 $50\%$ 的评测用例， $1≤n,m≤300$，$w_i=1$，$0≤k_i≤1$；

另存在 $20\%$ 的评测用例，$x_i=y_i$；

对于所有评测用例， $1≤n,m≤300000,0≤a_i≤10^6,1≤w_i≤10$，$0≤k_i≤10,1≤x_i≤y_i≤n$。保证数据中至少存在一个 $k_i=0$。