P3265 [JLOI2015] Equipment Purchase

Lian Ge is playing a magical game. There are $n$ pieces of equipment, each with $m$ attributes, represented by a vector $\mathbf{z_i} = (a_1, \ldots, a_j, \ldots, a_m)$ ($1 \le i \le n$, $1 \le j \le m$). Each piece of equipment costs $c_i$. Lian Ge wants to buy some equipment, but he is poor, so he always tries to spend as little money as possible to buy as many pieces as possible. For him, if the attributes of one piece of equipment can be formed by a combination of other purchased equipment (that is, he can use the equipment he owns to reproduce the effect of this piece), then this piece is unnecessary to buy. The strict definition is: if Lian Ge has bought $\mathbf{z_{i_1}}, \ldots, \mathbf{z_{i_p}}$, then for any undecided $\mathbf{z_h}$, if there do not exist $b_1, \ldots, b_p$ such that $b_1 \mathbf{z_{i_1}} + \ldots + b_p \mathbf{z_{i_p}} = \mathbf{z_h}$ ($b_i$ are real numbers), then Lian Ge will buy $\mathbf{z_h}$; otherwise, $\mathbf{z_h}$ is useless to him and need not be purchased. For example, let $\mathbf{z_1} = (1, 2, 3)$, $\mathbf{z_2} = (3, 4, 5)$, $\mathbf{z_h} = (2, 3, 4)$, and $b_1 = \frac{1}{2}$, $b_2 = \frac{1}{2}$. Then $b_1 \mathbf{z_1} + b_2 \mathbf{z_2} = \mathbf{z_h}$. In this case, if Lian Ge buys $\mathbf{z_1}$ and $\mathbf{z_2}$, he will not buy $\mathbf{z_h}$. Lian Ge wants to spend the minimum cost while buying the maximum number of pieces of equipment. Can you help him compute the result?

The first line contains two numbers $n, m$. The next $n$ lines each contain $m$ numbers; the $i$-th line describes the attribute values of equipment $i$. The next line contains $n$ numbers, where $c_i$ is the cost of buying the $i$-th piece of equipment.

Output one line with two numbers: the maximum number of pieces that can be purchased, and the minimum total cost under that maximum.

As described in the problem, choosing equipment $1$ and $2$, equipment $1$ and $3$, or equipment $2$ and $3$ are all valid, but choosing equipment $1$ and $2$ has the minimum cost, which is $2$. For $100\%$ of the testdata, $1 \le n, m \le 500$, $0 \le a_j \le 1000$. Translated by ChatGPT 5