Kuki's Struggle to Open a Restaurant

Kuki plans to run a restaurant for cats at Catholic University. Kuki believes the location matters most, so Kuki is working out the best spot.

Kuki surveyed the homes of $N$ cats and recorded each home's coordinates $(X, Y)$ and hunger level $Z$. No two cats live at the same coordinates.

In Kuki's country, there is a law: if a cat's home lies on a coordinate axis relative to a chosen point, the restaurant cannot be opened at that point. The restaurant may be placed at non-integer coordinates.

With the restaurant as the origin, define $S$ and $E$ as follows.

• $S_i$ = the sum of hunger levels $Z$ of the cats in quadrant $i$
• $E$ = (the maximum of $S_1, S_2, S_3, S_4$) minus (the minimum of $S_1, S_2, S_3, S_4$)
• If no cat is in quadrant $i$, $S_i$ is 0.
• If the restaurant cannot be opened at a point, $E$ is 100,000,000.

Kuki wants to open the restaurant where $E$ is smallest. Help Kuki find the minimum value of $E$.

The first line contains an integer $N$ ($4 \le N \le 1,000$).

Each of the next $N$ lines contains three integers $X$ ($-100,000,000 \le X \le 100,000,000$), $Y$ ($-100,000,000 \le Y \le 100,000,000$), and $Z$ ($1 \le Z \le 1,000$) describing one cat.

Print the minimum value of $E$.