题目描述

H 市是一座制造业十分发达的城市。在 H 市中，工厂可以生产 $n$ 种不同的物品，部分物品都可以以特定的价格 $a_i$ 在市场上售出而带来收益。生产方式分为两类，使用第一类生产方式每个工人可以在一天时间内生产若干件物品 $y$。使用第二类生产方式，每个工人可以在一天时间内使用若干件物品 $x$ 生产若干件物品 $y$，其中 $x \leq 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 \leq n, m \leq 300$，$w_i = 1$，$0 \leq k_i \leq 1$；
• 另存在 $20\%$ 的评测用例，$x_i = y_i$；
• 对于所有评测用例，$1 \leq n, m \leq 300000$，$0 \leq a_i \leq 10^6$，$1 \leq w_i \leq 10$，$0 \leq k_i \leq 10$，$1 \leq x_i \leq y_i \leq n$。保证数据中至少存在一个 $k_i = 0$。