Khalahar Zemuda, master of all Spiritual Sciences, has just discovered a new method to determine his client's karma. In order to determine it, he starts with a number of relevant zen characteristics (whose number depends on how much the person pays to obtain his/her karma) and, after communicating with the Gods, he assigns x y coordinates and a point-karma value to each of them.
Then, he determines the line-karma of each line in the 2D space by adding the point-karmas of all individual zen characteristics lying exactly on that line.
The person's karma (K) is equal to the maximum of such line-karmas.
Since you cannot automate the task of communicating with the Gods, this will be performed by Master Khalahar Zemuda himself, who then provides you with a list of zen points in 2D space, each with integer x y coordinates and integer point-karma values. Your goal is to find the karma (K) corresponding to such list.
Recall that a line can be described by the equation:
y = mx + b
where (0,b) is the y intercept of the line, i.e., the point where the line intercepts the y axis, and m is the slope.
Problem
Write a program that,
given a list of zen points in 2D space,
each with integer x y coordinates and integer point-karma values,
computes the corresponding karma (K).
Input
The input contains an unknown number of lists of zen points. However, the total number of zen points does not exceed 256.
Every list is preceded by an integer N specifying the number of points in that list. If N is 0, then there are no more lists.
Each of the following N lines contains the x coordinate (x),
the y coordinate (y) and the point-karma value (pk), in this order,
separated by a space,
where 0 <= x <= 100,
0 <= y <= 100 and
0 <= pk <= 100.
Output
The output contains the karma K (a positive integer) for each list in a separate line.
Sample Input
16 7 10 23 8 12 44 9 14 11 10 16 23 11 18 44 2 4 11 12 20 22 13 22 44 14 24 56 5 10 13 15 26 55 16 28 13 17 30 35 3 6 13 18 32 55 2 4 34 5 1 2 45 2 4 55 22 34 66 23 42 33 0 0 22 1 1 2 44 0
425 122 44