| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 345 | 92 | 69 | 26.538% |
역사와 전통을 자랑하는 제271회 UDPC의 개최를 위해 오늘도 수많은 운영진이 동분서주하고 있다. 운영진인 민호는 이전 대회들과 다르게, 개막식을 관현악 사중주로 시작해서 대회에 참여하는 사람들에게 더 풍성한 경험을 주고자 한다.
사중주는 여러 소리가 동시에 어우러져서 조화를 이루는 것이 중요한 만큼, 민호는 연주회의 조화도가 최대가 되도록 네 명의 학생을 선발해서 자리를 배치하려고 한다. 사중주는 네 명의 학생들이 일렬로 앉아서 연주를 진행하는 형태로 이루어진다.
UNIST, DGIST, POSTECH에는 악기를 잘 다루는 학생들이 다 합해서 $N$명이 있고, 이 중 $M$쌍의 학생들 사이에는 시너지가 존재한다. 어떤 시너지에 포함되는 두 학생이 모두 연주회에 참여하고, 두 학생의 연주 위치가 양옆으로 인접하다면 연주회의 조화도가 $d_i$만큼 상승하게 된다.
민호가 사중주에 참여할 학생들을 고르고 자리를 배치할 수 있는 모든 경우 중, 연주회의 조화도가 최대가 될 때의 그 값을 구해보자.
첫째 줄에는 후보 학생의 수 $N$과 시너지의 수 $M$이 주어진다. $(4\le N\le 200\ 000;0\le M\le 300\ 000)$
둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u_i,v_i,d_i$가 공백을 두고 주어진다. $u_i$번 학생과 $v_i$번 학생이 인접한 위치에서 연주하면 연주회의 조화도가 $d_i$만큼 상승한다는 의미이다. 어떤 두 학생 사이의 시너지는 최대 하나만 주어진다. $(1\le u_i<v_i\le N;1\le d_i\le 10^9)$
입력에서 주어지는 모든 수는 정수이다.
민호가 사중주에 참여할 네 명의 학생들을 고르고, 자리를 정하는 모든 경우 중에서 연주회의 조화도가 최대가 될 때의 값을 출력한다.
4 3 1 3 5 2 3 3 2 4 6
14
6 8 2 3 7 3 4 4 3 5 9 1 4 4 1 2 10 1 6 5 2 4 7 3 6 3
26