N수매화검법

시간 제한2초메모리 제한1024 MB

요약

가중치가 있는 N개의 선분을 한 번씩 실행할 때, 아직 실행되지 않은 교차 선분 수에 따라 드는 내공의 최솟값을 구합니다.

난이도: 보통10점 중 6점
유형: 그리디, 기하
정답자: 아직 제출이 없습니다

문제

화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로, 총 $N$ 개의 베기(검으로 무언가를 베는 동작)로 이루어진다.

N수매화검법은 2차원 평면 위에서 펼치는 검법이다. 베기 $i$ 는 점 $s_i$ 에서 시작해 $e_i$ 까지 일직선으로 벤다. 이때 검이 지나는 경로를 베기 $i$ 의 경로라고 한다.

검법을 펼치는 동안 베기를 한 번 할 때마다 심오한 원리에 따라 내공을 소모한다. 그 원리는 다음과 같다.

베기 $i$ 에는 가중치 $w_i$ 가 정해져 있으며, 베기 $i$ 를 행하면 $(m+1)\times w_i$ 만큼의 내공을 소모한다. 이때 $m$ 은 베기 $i$ 를 행한 순간에 아직 행하지 않은 베기 중 베기 $i$ 의 경로와 교차하는 베기의 개수다.

N수매화검법을 완성하려면 $N$ 개의 베기를 모두 정확히 한 번씩 행해야 하며, 순서는 상관없다. 장로 우경은 내공을 최소한으로 소모하여 N수매화검법을 완성하고 싶어 한다. 이를 위해 N수매화검법을 완성하는 데 소모해야 하는 내공 합의 최솟값을 구해 주자.

입력

첫 번째 줄에 베기의 개수 $N$ 이 주어진다. $(1 \le N \le 2\,500)$

다음 $N$ 개의 줄에는 각 줄마다 베기 $i$ 에 대해 $s_i$ 의 좌표 $(sx_i, sy_i)$ , $e_i$ 의 좌표 $(ex_i, ey_i)$ , 가중치 $w_i$ 가 공백으로 구분되어 차례로 주어진다. $(-10^9 \le sx_i, sy_i, ex_i, ey_i \le 10^9$ ; $1 \le w_i \le 10^9)$

주어지는 $2N$ 개 점의 위치는 모두 서로 다르며, 어떤 세 점도 같은 직선 위에 있지 않다.

입력으로 주어지는 모든 수는 정수다.

출력

N수매화검법을 완성하는 데 소모해야 하는 내공 합의 최솟값을 출력하라.

예제1

예제 1
입력
```
3
1 1 3 3 1
1 3 3 1 2
6 7 8 9 1
```
예상 출력
```
5
```