### 2016 Canadian Computing Olympiad

## Day 1, Problem 2 - Splitting Hares

As you know, some bunnies are good bunnies, and some bunnies are bad bunnies.

You are given the location of all the bunnies, and their "goodness" weight (a positive integer for good bunnies and a negative integer for bad bunnies). No two bunnies are at the same location. Divide them into two groups using a straight line such that the sum of the "goodness" of the bunnies on one side of the line is as large as possible. A bunny on the line is counted in the sum of the weights on both sides of the line.

### Input Format

The first line contains `N` (2 ≤ `N` ≤ 4000), the number of bunnies. The next `N` lines contain three space-separated integers: `x _{i}`

`y`

_{i}`w`, which indicates that at the point (

_{i}`x`,

_{i}`y`) there is a bunny with a goodness weight of

_{i}`w`(−1 000 000 ≤

_{i}`x`≤ 1 000 000; −1 000 000 ≤

_{i}`y`≤ 1 000 000; −10 000 ≤

_{i}`w`≤ 10 000). The locations (

_{i}`x`,

_{i}`y`) will be distinct (i.e., there is no other

_{i}`j`≠

`i`such that (

`x`,

_{i}`y`) = (

_{i}`x`,

_{j}`y`)).

_{j}
For 5 of the 25 marks available, `N` ≤ 200 and no three locations are collinear.

For an additional 10 of the 25 marks available, no three locations are collinear.

### Output Format

Output the maximum sum of weights that is possible by drawing a straight line and picking all the bunnies which are on one side of that line.

### Sample Input

6 1 8 4 1 4 6 7 7 2 4 10 -3 4 6 -9 4 2 8

### Sample Output

18

### Explanation

Take the bunnies with goodness weights of 4, 6 and 8, which are on the "left" side of the line, as shown in the diagram below:

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 15.00s

**Memory Limit:** 16M

**Added:** May 14, 2016

**Author:** nullptr

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...