BBC7HVectors
vreme | memorija | ulaz | izlaz |
---|---|---|---|
0,5 s | 16 Mb | standardni izlaz | standardni ulaz |
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 + λ2 v2 + ... + λm vm = 0 are λ1 = λ2 = ... = λm = 0. For example, in R2 the set of vectors {(1 0), (0 1)} is linearly independent. However, {(1 0), (0 1), (1 1)} is not since 1 ∙ (1 0) + 1 ∙ (0 1) + (-1) ∙ (1 1) = (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.
- 1 ≤ d ≤ 200
- 1 ≤ n ≤ 500
- The coordinates of the vectors are integers in the range [-103,103].
- The weights of the vectors are integers in the range [-106,106].
4 4
1 0 0 0 30
0 0 1 0 30
1 0 1 0 100
0 0 0 1 1
131
Morate biti ulogovani kako biste poslali zadatak na evaluaciju.