Vectors
By Luka Milićević 
Serbia
By Luka Milićević Serbia
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 λ1,λ2,...λM that satisfy λ1,v1+λ2v2+...+λMvM=0 are λ1=λ2=...=λ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.
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.
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 |