题目描述

傲娇少女幽香是一个很萌很萌的妹子，这些天幻想乡的大家都不知道为何还是拼命喝酒。很快酒就供不应求了，为了满足大家的需求，幽香决定在森林里酿酒。

经过调查，幽香发现森林里面有一些地方非常适合酿酒，有一些地方则非常适合存酒。
幽香把这些适合酿酒的地方称为酿酒点，不妨认为有 $n$ 个酿酒点，从 $1$ 到 $n$ 标号。
同时也有 $m$ 个适合存酒的地方，幽香将它们称为存酒点，从 $1$ 到 $m$ 标号。
在一些酿酒点和存酒点之间存在通道，如果酿酒点 $i$ 到存酒点 $j$ 之间存在通道，那么 $i$ 生产的酒就可以被运输到 $j$。

但是在一个地方酿酒是需要消耗幽香的魔力的，由于存在管理上的因素，在酿酒点 $i$，制造 $x$ 升的酒，需要花费 $a_ix^2+b_ix$ 的魔力，注意 $x$ 不一定是一个非负整数，也可以是一个非负实数，同时在这个点最多只能制造 $c_i$ 升的酒。

每个存酒点 $j$ 有一个容量 $d_j$，表示这个存酒点最多能存多少升的酒。幽香打算存尽量多的酒，那么她需要在一些酿酒点生产一些酒并且通过通道将酒运送到存酒点。

当然幽香想要节省自己的魔力，所以想让你帮忙算出在满足要求的情况下，最少花费的魔力是多少？

输入格式

第一行两个正整数 $n,m$，表示酿酒点和存酒点的数量。
接下来 $n$ 行，第 $i$ 行三个数 $a_i,b_i,c_i$，表示在酿酒点i制造酒的花费系数，和上限。
接下来一行 $m$ 个整数，依次为每个存酒点的 $d_i$ 值。
接下来 $n$ 行，每行 $m$ 个数，其中第 $i$ 行第 $j$ 个表示酿酒点 $i$ 到存酒点 $j$ 有没有通道（$1$ 表示有，$0$ 表示没有）。

输出格式

输出第一行表示幽香最多能存多少升酒（注意这肯定是个整数，直接输出即可）。
输出一行表示最小花费魔力，注意这肯定是一个有理数，化简后按照 a/b 的形式输出（$0$ 输出 0/1）。

样例

input

10 10
0 2 3
2 3 2
3 1 3
1 2 1
1 0 1
1 1 0
3 3 0
1 2 2
3 1 1
3 1 0
3 1 2 2 3 1 1 2 2 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0
1 0 1 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0

output

8
42/1

数据范围与提示

对于 $30 \%$ 的数据：所有 $a_i=0$。
对于另 $30 \%$ 的数据：最终答案的分母$\leq 1000$。
对于 $100 \%$ 的数据：$1 \leq n \leq 100, \ 1 \leq m \leq 100$。
对于所有数据，$0 \leq a_i,b_i,c_i,d_i \leq 3$且都是整数。同时对于每个 $i$，$a_i+b_i>0$ 通道的数量不超过 $1000$ 条。
非常神奇的是，对于所有数据存在一个正整数 $X \leq 10^7$，使得存在一个最优解，使得所有路径上运送的酒的体积都是 $1/X$ 的倍数。