URI Online Judge | 3073

# Vectors

By Luka Milićević 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