Minimum Cost Maximum Equipment Selection

Facebrother is playing an amazing game. In this game, there are (n) pieces of equipment, where each equipment has (m) attributes represented by the vector (\mathbf{z_i} = (a_1, \ldots, a_m)) for (1 \leq i \leq n), and each equipment costs (c_i). Being short on cash, he wants to purchase equipment in such a way that he obtains as many pieces as possible while spending as little money as possible.

More precisely, suppose he has already purchased equipment with attribute vectors (\mathbf{z_{i_1}}, \mathbf{z_{i_2}}, \ldots, \mathbf{z_{i_p}}). For any equipment with attribute vector (\mathbf{z_h}), he will only buy it if there do not exist real numbers (b_1, b_2, \ldots, b_p) such that [ b_1\mathbf{z_{i_1}} + b_2\mathbf{z_{i_2}} + \cdots + b_p\mathbf{z_{i_p}} = \mathbf{z_h} ] In other words, if (\mathbf{z_h}) lies in the span of the equipment he has already bought, it is considered redundant and will not be bought.

Your task is to help him calculate the minimum total cost required to purchase a maximum set of equipment, i.e. a set that is as large as possible (which will be a basis for the vector space spanned by the equipment) and, among all such sets, has the minimum possible total cost.

inputFormat

The input begins with two integers (n) and (m) (e.g. (1 \leq n \leq 10^5) and (1 \leq m \leq 10)). Each of the following (n) lines contains (m+1) integers. The first (m) integers on a line denote the attributes (a_1, a_2, \ldots, a_m) of an equipment, and the last integer denotes its cost (c_i) ((1 \leq c_i \leq 10^9)).

outputFormat

Output a single integer representing the minimum total cost required to purchase a maximum set of equipment (i.e. a maximum linearly independent set).

sample

3 3
1 2 3 10
3 4 5 20
2 3 4 15

25