스키 코스
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
이번 겨울에는 친구들과 스키장으로 놀러가기로 하였다. 스키장은 산자락에 지어져 있었고, 슬로프가 굉장히 다양했다. 볼거리가 많기로 유명한 슬로프들도 있었고, 보잘것 없는 슬로프도 있었다.
산에는 지점이 N개 있다. 모든 지점은 1 이상 N 이하의 정수로 번호가 매겨져 있다. 지점의 번호는 높이 순서에 따라 붙여진다. 지점의 번호가 증가하면 높이는 감소한다. 1번 지점이 가장 높고, N번 지점이 가장 낮다. 각 지점의 높이는 정해져있고, 모든 지점은 높이가 다르다. 일부 지점들 사이에는 스키를 타고 이동할 수 있는 슬로프가 있다.
스키를 한번 타기 시작하면 슬로프를 내려가는 것밖에 할 수 없다. 낮은 지점에서 높은 지점으로 올라가는 것은 불가능하다.
각 슬로프에는 흥미도가 매겨져 있고, 수치가 클수록 재미있는 슬로프이다. 반대로 너무 지루해서 흥미도가 음수인 슬로프도 있을 수 있다.
찬민이는 이러한 산에서 스키를 한 번 타려고 한다. 스키를 타고 슬로프를 따라 내려가기만 하고, 다른 지점으로 가기 위해서는 반드시 슬로프를 타고 내려가려고 한다. 하지만 체력이 좋지 않아서 슬로프는 최대 S개만 사용하고 싶어한다. 최대 S개의 슬로프만 사용한다고 할 때, 찬민이는 지나게 되는 슬로프의 흥미도의 합을 최대화 하고 싶다. 출발 지점은 찬민이가 목표를 달성하기 위해 원하는 대로 고를 수 있다. 경우에 따라서는 슬로프를 하나도 이용하지 않아도 된다.
입력
입력의 첫 줄에는 테스트 케이스의 개수를 의미하는 정수 T( \le 100)이 주어진다.
각 테스트 케이스의 첫 줄에 세 정수 N(1 \le N \le 50,000), M(0 \le M \le 100,000), S(1 \le S \le 100)가 빈 칸을 사이에 두고 주어진다.
N은 스키장에 있는 지점의 개수, M은 스키장에 있는 슬로프의 개수, S는 최대 이용 가능한 슬로프의 개수이다.
그 다음 M개의 줄에 세 정수 A_i, B_i, C_i가 빈 칸을 사이에 두고 주어진다.
(1 \le i \le M) 1 \le A_i < B_i \le N이고, -100,000 \le C_i \le 100,000이다.
A_i와 B_i는 슬로프가 잇는 두 지점의 번호를 의미하고, C_i는 해당 슬로프의 흥미도를 나타낸다.
출력
각 테스트케이스마다 최대 S 개의 슬로프를 연속으로 이용하여 얻을 수 있는 흥미도의 합의 최대값을 한 줄에 출력한다.
예제 입력
2 4 5 2 1 2 10 1 3 20 2 3 50 2 4 25 3 4 15 4 5 2 1 2 -5 1 3 20 2 3 50 2 4 25 3 4 -20
예제 출력
65 50
노트