시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)111243934139.790%

문제

화산파의 장로 우경은 새로운 무공 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$, $e_i$의 좌표 $(\mathit{sx}_i,\mathit{sy}_i)$, $(\mathit{ex}_i,\mathit{ey}_i)$와 가중치 $w_i$가 공백으로 구분되어 차례로 주어진다. $(-10^9\le\mathit{sx}_i,\mathit{sy}_i,\mathit{ex}_i,\mathit{ey}_i\le 10^9$; $1\le w_i\le 10^9)$

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

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

출력

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

예제 입력 1

3
1 1 3 3 1
1 3 3 1 2
6 7 8 9 1

예제 출력 1

5