問題
당신은 스키어 무리를 인솔하고 있다. 스키어들은 하루 동안 대여한 큰 산으로 여행을 왔다.
산에는 1번부터 N번까지 번호가 매겨진 N개의 휴식 지점(rest point)이 있고, 이들을 잇는 N-1개의 슬로프가 있다. 각 슬로프는 어떤 휴식 지점에서 시작해 다른 휴식 지점으로 곧바로 이어지며, 중간에 다른 슬로프나 휴식 지점은 없다. 또한 각 슬로프는 오직 한 방향으로만 내려갈 수 있다.
각 스키어는 정상에 있는 휴식 지점에서 출발해 어떤 슬로프를 타고 다른 휴식 지점으로 내려간다. 그곳에서 또 다른 슬로프를 타고 더 내려갈 수도 있고, 이런 식으로 계속할 수 있다. 스키어가 자신의 목적지 휴식 지점에 도착하면 그날의 스키를 끝내고, 스키 로지로 가서 따뜻한 코코아를 마신다. 목적지 휴식 지점은 정상 휴식 지점일 수는 없다. 다만, 스키어의 목적지 휴식 지점은 다른 슬로프들의 시작점이 될 수도 있다는 점에 유의하라. 즉, 이용할 수 있는 슬로프가 남아 있더라도 반드시 끝까지 타야 하는 것은 아니고, 언제든지 남은 구간은 조심히 걸어서 내려갈 수 있다! 모든 휴식 지점에 대해, 정상 휴식 지점에서 출발해 그 지점에 도달하는 데 사용할 수 있는 슬로프들의 순서는 정확히 하나뿐이다.
각 슬로프는 하루 동안 수용할 수 있는 스키어 총합이 정해져 있으며, 그 수를 넘기면 눈이 너무 울퉁불퉁해져 스키를 타기 어렵다. 또한 스키 리조트는 스키어가 각 슬로프를 탈 때마다 요금을 받거나 보상금을 줄 수 있다. 슬로프마다 요금은 다를 수 있고, 각 스키어는 자신이 탄 각 슬로프에 대해 그 요금을 지불해야 한다. 슬로프의 요금은 양수일 수도, 0일 수도, 심지어 음수일 수도 있는데, 음수인 경우는 그 슬로프를 시험 주행해 준 것에 대한 보상금(바운티)을 뜻한다. 당신은 인솔자로서 스키어들을 대신해 모든 요금을 지불하고 모든 보상금을 수령한다. 같은 슬로프를 여러 스키어가 이용하면, 그 슬로프의 요금을(혹은 보상금을) 그만큼 여러 번 지불(혹은 수령)한다는 점에 유의하라. 당신이 지불한 모든 비용의 합에서 수령한 모든 보상금의 합을 뺀 값이 이번 여행의 총지출이다. 총지출은 양수, 0, 음수 모두 가능하다. 총지출이 음수라면, 오히려 이번 여행으로 돈을 벌었다는 뜻이다!
인솔자로서, 당신은 산에 올릴 수 있는 스키어 수의 최댓값을 알고 싶다. 또한 그 최댓값의 스키어를 올렸을 때 가능한 총지출의 최솟값도 알고 싶다.
入力
입력의 첫 줄에는 테스트 케이스 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 정수 N이 주어지며, 이는 산에 있는 휴식 지점의 개수이다.
그 다음 N-1줄에는 각 슬로프를 나타내는 네 정수 Ui, Vi, Si, Ci가 주어진다. 이는 각각 슬로프의 시작 휴식 지점, 슬로프의 도착 휴식 지점, 그 슬로프가 하루 동안 수용할 수 있는 스키어의 최대 수, 그리고 스키어 1명당 그 슬로프의 요금(가격)을 의미한다.
스키어들이 출발하는 정상 휴식 지점의 번호는 항상 1이다.
出力
각 테스트 케이스마다 Case #x: y z 형식의 한 줄을 출력하라.
여기서 x는 (1부터 시작하는) 테스트 케이스 번호이고,
y는 스키어 수의 최댓값,
z는 스키어 y명이 각각 적어도 하나의 슬로프를 타도록 했을 때의 총지출 최소값이다.
例題
2
4
1 2 2 5
1 3 2 5
3 4 1 -2
7
4 7 2 2
1 3 5 5
1 4 2 -1
3 2 3 -2
3 5 2 -1
3 6 2 2
Case #1: 4 18
Case #2: 7 15
ログインしないとコードを書けません。