cho.sh정화조
아직 제출이 없습니다시간 제한3초메모리 제한512 MB문제
경곽에는 아주 거대한 정화조 시설이 있다. 정화조의 구조는 다음과 같다. 먼저 원천(source)에서 여러 개의 펌프를 이용해서 물을 퍼 올린다. 물은 수도관을 따라 여러 정화조 시설을 거치게 된다. 수도관은 한 정화조와 다른 정화조를 이어주는 역할을 한다. 수도관은 트리 형태의 간선 구조를 가지고 있다. 다시 말하면 수도관을 따라 물이 이동할 때 한 정화조를 두 번 이상 지나지 않으며, 펌프에서 퍼 나른 물들은 모두 최종적으로 한 정화조로 모이는 구조를 지니고 있다. 위 그림에서 동그라미는 정화조를, 화살표는 수도관을 나타낸 것이다. 펌프에서 퍼 올린 물은 최초로 트리의 리프에 존재하는 정화조로 이동한다. (여기서 리프란 자기에게로 향하는 수도관이 없는 정화조를 의미한다.)
물은 수질에 따라 여러 등급으로 분류할 수 있다. 가장 깨끗한 물은 0등급이고, 1등급, 2등급, 3등급, 순으로 물이 더러워진다. 처음에 원천에서의 물은 0등급이다. 물이 수도관을 따라 한 정화조에서 다른 정화조로 이동할 때마다 물은 오염되고 수질은 한 등급 오른다. 정화조에 처음 도착한 물의 수질도 1등급이라고 본다.
물이 정화조를 지날 때, 정화조는 이 물을 정화할 수도 있고, 그대로 흘려보낼 수도 있다. 정화조에는 고유 비용 가 존재한다. 정화조에서 물을 정화할 경우, × (정화할 물의 수질 등급) 만큼의 비용이 소모되며, 물은 0등급으로 정화된다. 만약 물을 정화하지 않을 경우, 아무 비용도 지출하지 않으며 물의 수질도 변하지 않는다.
정화조의 효율적인 운영을 위해 각 정화조마다 두 수 , () 가 주어진다. 이는 번째 정화조는 이상 이하 등급의 수질을 갖는 물만 정화할 수 있다는 의미이다.
경곽은 막대한 정화조 공사를 위해 일시적으로 정화조의 운영을 중단하려고 한다. 정화조의 운영을 중단한다는 것은 물이 그 정화조를 지나갈 수 없도록 만든다는 것이다. 다만 경곽으로의 물 공급이 끊기면 안 되기 때문에, 몇 가지 정화조는 그대로 운영하려고 한다. 경곽에겐 쿼리가 주어진다. 각 쿼리에는 정화조 번호 와 수질 가 주어진다. 경곽은 원천과 정화조 를 잇는 한 경로를 제외하고 나머지 정화조는 모두 중단하려고 한다. 이때, 에서 등급 이하의 물을 얻으려면 최소 몇의 비용을 필요로 하는지 구해야 한다.
경곽의 문제를 같이 해결해 주자. 쿼리는 다른 쿼리와 서로 독립적이다. 즉, 한 쿼리에서 중단시킨 정화조가 다음 쿼리에서도 무조건 중단되는 것은 아니다.
입력
첫 번째 줄에 정화조의 개수 이 주어진다.
두 번째 줄에 개의 정수 이 주어진다. 는 번째 정화조의 고유 비용을 의미한다.
다음 개의 줄에 걸쳐 수도관이 정화할 수 있는 수질 등급의 범위 가 주어진다.
다음 개의 줄에 걸쳐 수도관에 대한 정보가 주어진다. 각 줄에는 이 주어진다.
이는 번째 정화조에서 번째 정화조로 수도관이 이어져 있다는 것을 의미한다.
다음 줄에는 쿼리의 개수 가 주어진다.
다음 개의 줄에 걸쳐 각 줄에 두 정수 가 주어진다.
이는 정화조 와 원천을 잇는 한 경로에서 이하의 수질 등급을 얻으려고 할 때 필요한 최소 비용을 출력하라는 의미이다.
출력
개의 줄에 걸쳐 각 쿼리에 대한 답을 한 줄에 하나씩 출력한다.
만약 이하의 수질 등급의 물을 얻을 수 없다면 -1을 출력한다.
제한
- ,