The young girl Youxiang is a very, very cute girl. Everyone in this fantasy land doesn't know when she started drinking heavily. Soon, she couldn't satisfy her cravings, so to meet everyone's needs, Youxiang decided to brew wine in the forest.

After investigation, Youxiang found that there are some places in the forest that are very suitable for brewing wine, and some places are very suitable for storing wine.

Youxiang calls these places suitable for brewing "breweries," and we can assume there are $n$ breweries, numbered $1$ to $n$.

At the same time, there are $m$ places suitable for storing wine, and Youxiang calls them "storage points," numbered $1$ to $m$.

There are paths between some breweries and storage points. If there is a path between brewery $i$ and storage point $j$, then the wine produced by $i$ can be transported to $j$.

However, brewing wine in some places consumes Youxiang's magic power. Due to management factors, producing $x$ liters of wine at brewery $i$ requires $a_i x^2 + b_i x$ magic power. Note that $x$ does not have to be an integer; it can be a non-integer. At the same time, this location can produce at most $c_i$ liters of wine.

Each storage point has a capacity $d_j$, which represents the maximum amount of wine this storage point can store. Youxiang plans to store as much wine as possible. Since there are only breweries in the forest that can brew wine, and only storage points that can store wine, she needs some breweries to produce some wine and transport it to the storage points through the paths.

Naturally, Youxiang wants to save her magic power, so she wants you to help her calculate the minimum magic power required to satisfy the requirements.

Input

The first line contains two positive integers $n$ and $m$, representing the number of breweries and storage points.

Next $n$ lines, each line contains three integers $a_i, b_i, c_i$, representing the cost coefficient and upper limit for brewery $i$ to produce wine.

Next one line contains $m$ integers, representing the $d_j$ values for each storage point in order.

Next $n$ lines, each line contains $m$ integers, where the $j$-th integer in the $i$-th line indicates whether there is a path between brewery $i$ and storage point $j$ ($1$ for yes, $0$ for no).

Output

Output the first line representing the maximum amount of wine Youxiang can store (note that this must be an integer, just output it directly).

Output the second line representing the minimum magic power cost. Note that this must be a rational number; simplify it and output it in the form $a/b$ ($0$ should be output as $0/1$).

Constraints

For $30\%$ of the data: all $a_i = 0$.

For another $30\%$ of the data: the denominator of the final answer $\le 1000$.

For $100\%$ of the data: $1 \le n \le 100, 1 \le m \le 100$.

For all data: $0 \le a_i, b_i, c_i, d_j \le 300$ are all integers. At the same time, for each $i$, $a_i + b_i > 0$, and the number of paths does not exceed $500$.

It is amazing that for all data, there exists a positive integer $X \le 10^{12}$ such that the optimal solution makes the volume of wine transported on all paths a multiple of $1/X$.

Examples

Input 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

Output 1

8
42/1