시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 301 | 55 | 39 | 27.273% |
졸업논문을 완성하지 못한 형서는 학교에 대한 테러 계획을 세웠다. 고급정보과학 시간에 몰래 형서가 제작한 기계는, 전원을 켠 순간부터 폭주하기 시작해서 온 학교를 쑥대밭으로 만들고 있다. 으악!
학교를 살려내기 위해서, 박종화 선생님은 형서의 설계도를 입수했다. 설계도에 의하면, 폭주 기계에는 n개의 장비가 존재하며, 현재 1번 장비만이 폭주하고 있다. 장비를 정지시키기 위해서는, 박종화 선생님이 각각의 장비에 전기 충격을 가해야 한다.
설계도에 의하면, 전기 충격에는 약한 충격과 강한 충격이 있다. i번 장비에 약한 충격을 가하는 데는 ui 와트의 전력이 필요하며, 강한 충격을 가하는 데는 zi 와트의 전력이 필요하다. (ui < zi) 약한 충격과 강한 충격 모두 i번 장비를 정지시키지만, 약한 충격을 받았을 때는, ri 개의 특정한 장비들이 다시 작동을 시작하게 된다! 각각의 장비에 대해서, 이러한 특정한 장비들은 gi,1, ..., gi,ri 와 같은 리스트로 표현 가능하며, 이 리스트 역시 설계도에 적혀 있다.
박종화 선생님은 모든 장비를 정지하려고 한다. 하지만, 학교는 난장판이 되었고, 공급받을 수 있는 전력량에는 한계가 있다. 박종화 선생님은 전기 충격에 사용한 전력의 합의 최솟값을 구하려고 한다. 힘을 합쳐서 박종화 선생님을 도와드리자.
첫 번째 줄에는 장비의 개수를 뜻하는 정수 n이 주어진다. (1 ≤ n ≤ 200, 000).
이후 n개의 줄에 장비의 정보가 순서대로 주어진다. 이 중 i번째 줄은 장비 i의 정보를 나타낸다. 각각의 줄에는 먼저 세 정수 ui, zi, ri 가 주어지며 (1 ≤ ui < zi ≤ 109, 1 ≤ ri), 이후 ri개의 정수 gi,1, ..., gi,ri (1 ≤ gi,j ≤ n) 가 주어진다. 모든 i에 대해 ri의 합은 106을 넘지 않는다. 다시 작동을 시작하는 장비의 리스트에, 같은 원소가 여러 번 등장할 수 있으며, 이때는 해당 장비를 등장 횟수만큼 종료해야 한다.
모든 장비를 정지하기 위해 필요한 전력량의 최솟값을 출력하라.
4 4 27 3 2 3 2 3 5 1 2 1 13 2 4 2 5 6 1 2
26