Description

The tsundere girl Yuuka is a very cute girl. Recently, for some reason, everyone in Gensokyo has been drinking like crazy. Soon the supply of alcohol cannot keep up with demand. To meet everyone’s needs, Yuuka decides to brew alcohol in the forest.

After investigation, Yuuka finds that some places in the forest are very suitable for brewing, while others are very suitable for storage. She calls the places suitable for brewing the brewing sites. Assume there are $n$ brewing sites, numbered from $1$ to $n$. There are also $m$ storage sites, numbered from $1$ to $m$. There are channels between some brewing sites and storage sites. If there is a channel between brewing site $i$ and storage site $j$, then the alcohol produced at $i$ can be transported to $j$.

Brewing at a site consumes Yuuka’s magic. Due to management factors, at brewing site $i$, producing $x$ liters of alcohol costs $a_i \cdot x^2 + b_i \cdot x$ magic. Note that $x$ does not have to be a nonnegative integer; it can be any nonnegative real number. Also, at this site at most $c_i$ liters can be produced. Each storage site $j$ has a capacity $d_j$, meaning this storage site can store at most $d_j$ liters of alcohol.

Yuuka plans to store as much alcohol as possible, so she will produce some alcohol at certain brewing sites and transport it through the channels to the storage sites. Of course, Yuuka wants to save her magic, so please help her compute, under the requirement of storing the maximum possible amount, what the minimum magic cost is.

Input Format

The first line contains two positive integers $n$, $m$, the numbers of brewing sites and storage sites. The next $n$ lines, on the $i$-th line are three numbers $a_i$, $b_i$, $c_i$, representing the cost coefficients and the production upper bound at brewing site $i$. The next line contains $m$ integers, which are the values $d_j$ for each storage site in order. Then there are $n$ lines, each containing $m$ numbers. On the $i$-th line, the $j$-th number indicates whether there is a channel from brewing site $i$ to storage site $j$ ($1$ means there is, $0$ means there is not).

Output Format

Output the first line as the maximum total liters of alcohol Yuuka can store (note that this is always an integer; just output the integer).

Output the second line as the minimum magic cost. This is always a rational number; after reduction, output it in the form $a/b$ (if it is $0$, output $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

• For $30\%$ of the testdata: all $a_i = 0$.
• For another $30\%$ of the testdata: the denominator of the final answer is $\leq 1000$.
• For $100\%$ of the testdata: $1 \leq n \leq 100$, $1 \leq m \leq 100$.
• For all testdata, $0 \leq a_i, b_i, c_i, d_i \leq 3$ and all are integers. Also, for each $i$, the number of channels with $a_i + b_i > 0$ does not exceed $1000$.
• Interestingly, for all testdata there exists a positive integer $X \leq 10^7$ such that there is an optimal solution where the amount transported on every path is a multiple of $1/X$.

Translated by ChatGPT 5