URI Online Judge | 3073

Vectors

By Luka Milićević RS Serbia

Timelimit: 1

A set of M vectors {v1, v2,...,vM} in Rd (the set of d-tuples of real numbers) is said to be linearly independent if the only reals λ12,...λM that satisfy λ1,v1+λ2v2+...+λMvM=0 are λ12=...=λM=0. For example, in R2 the set of vectors {\({\binom { 0 } { 1 }, \binom { 0 } { 1 } }\)} is linearly independent. However, {\(\binom { 0 } { 1 }, \binom { 0 } { 1 }, \binom { 1 } { 1 }\)} is not since \(1\binom { 1 } { 0 }+1\binom { 0 } { 1 }+(-1)\binom { 1 } { 1 }=\binom { 0 } { 0 }\).

In this task, you are given N vectors in Rd , and every vector has some weight. Your job is to find a linearly independent set of vectors with maximal sum of weights.

Input

The first line contains two integers d and N . The next N lines contain d+1 integers each, separated with one empty space between any two integers. The first d numbers in the line i+1 are coordinates of the ith vector, and the last number is its weight.

Output

The output should consist a single integer: the sum of weights of vectors in your set.

Input Sample Output Sample

4 4

1 0 0 0 30

0 0 1 0 30

1 0 1 0 100

0 0 0 1 1

131