시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 1112 | 439 | 341 | 39.790% |
화산파의 장로 우경은 새로운 무공 N수매화검법을 창안했다. N수매화검법은 이십사수매화검법을 발전시킨 검법으로 총 $N$개의 베기(검으로 무언가를 베는 동작)로 이루어진다.
N수매화검법은 2차원 평면 상에서 펼치는 검법으로, 베기 $i$는 점 $s_i$에서 시작해 $e_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수매화검법을 완성하는 데 소모해야 하는 내공의 합의 최솟값을 출력하라.
3 1 1 3 3 1 1 3 3 1 2 6 7 8 9 1
5