N-Sumaehwa Sword Technique

Time limit2sMemory limit1024 MB

Summary

Order N weighted line segments so that the total cost is minimized, where each stroke costs its weight times one plus the number of unperformed segments it crosses.

Level: Medium6 of 10
Topics: Greedy, Geometry
Solved: No attempts yet

Problem

Elder Woo Kyung of Hwasan Sect created a new martial art, N-Sumaehwa Sword Technique. It is an advanced version of the Twenty-Four Sumaehwa Sword Technique and consists of $N$ strokes (cuts made with the sword).

The technique is performed on a two-dimensional plane. Stroke $i$ cuts in a straight line from point $s_i$ to point $e_i$ . The path the sword travels is called the path of stroke $i$ .

While performing the technique, each stroke costs internal energy according to the following principle.

Stroke $i$ has a weight $w_i$ . Performing stroke $i$ costs $(m+1)\times w_i$ units of internal energy, where $m$ is the number of strokes not yet performed at that moment whose paths intersect the path of stroke $i$ .

To complete the N-Sumaehwa Sword Technique, each of the $N$ strokes must be performed exactly once, in any order. Elder Woo Kyung wants to complete the technique using as little internal energy as possible. Find the minimum total internal energy needed to complete the N-Sumaehwa Sword Technique.

Input

The first line contains the number of strokes $N$ . $(1 \le N \le 2\,500)$

Each of the next $N$ lines gives, for stroke $i$ , the coordinates $(sx_i, sy_i)$ of $s_i$ , the coordinates $(ex_i, ey_i)$ of $e_i$ , and the weight $w_i$ , separated by spaces. $(-10^9 \le sx_i, sy_i, ex_i, ey_i \le 10^9$ ; $1 \le w_i \le 10^9)$

The $2N$ points are all distinct, and no three of them lie on the same straight line.

All numbers in the input are integers.

Output

Print the minimum total internal energy needed to complete the N-Sumaehwa Sword Technique.

Examples1

Example 1
Input
```
3
1 1 3 3 1
1 3 3 1 2
6 7 8 9 1
```
Expected output
```
5
```