N수매화검법

화산파의 장로 우경은 새로운 무공 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수매화검법을 완성하는 데 소모해야 하는 내공의 합의 최솟값을 출력하라.