题目描述

傲娇少女幽香是一个很萌很萌的妹子，这些天幻想乡的大家都不知道为何还是拼命喝酒。很快酒就供不应求了，为了满足大家的需求，幽香决定在森林里酿酒。 经过调查，幽香发现森林里面有一些地方非常适合酿酒，有一些地方则非常适合存酒。 幽香把这些适合酿酒的地方成为酿酒点，不妨认为有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）。

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

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

提示

没有写明提示

题目来源

没有写明来源