Informatica Online Judge

  강의 하류 [1294 / 050E]

Time Limit(Test case) : 1500(ms)
Number of users who solved : 4   Total Tried : 110


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 김지성)]

Background

경곽이의 나라는 황산이 흐르는, 아주 기다란 강의 하류에 자리잡고 있다.

갑작스럽지만, 홍수가 났다! 홍수로 인해 엄청난 물이 경곽이의 나라로 내려오고 있고, 경곽이는 조금이라도 오래 살기 위해 최대한 물이 내려오는 속도를 늦춰야 한다.

우선, 이 강의 구조를 조사해 본 결과 다음과 같이 n개의 노드가 있는 트리 형태의 강이였다.



경곽이의 나라는 항상 제일 밑인 1번에 위치해 있고, 물은 노드로 표시된 지점들을 타고 내려온다.

노드들 사이에는 간선이 있어서 물은 간선을 통해서만 흘러 내려오며, i번째 간선을 타고 물이 내려오는 데 걸리는 시간(=간선의 길이) ai로 정의된다.

각각의 지점에는 장치가 설치되어 있어서 물을 막아둘 수 있고, i번 지점에서 1만큼의 물을 1의 시간동안 막는 데 필요한 비용은 bi로 정의된다.

물을 막아두는 장치는 자유롭게 사용할 수 있다. 다시 말해서, 지점에 들어오는 물을 전부 막지 않고 일부를 흘려내려도 되며, 원할 때 물을 막고 흘려보낼 수 있다.

물은 막아두지 않으면 지점에 도달하자마자 다시 아래로 흐르기 시작한다.

물은 m개의 근원지로부터 출발한다. i번째 근원지의 초기 물의 양 ci 로 정의된다.

물이 단 1이라도 경곽이의 나라에 도달하는 순간, 경곽이의 나라는 몰락한다.

경곽이의 나라는 세수 부족으로 인해 최대 k만큼의 비용을 사용할 수 있다.

이 때, 경곽이의 나라 국민들이 살 수 있는 최장 일수를 출력하라.

Input

첫째 줄에 지점의 갯수 n과, 물의 근원지 m과, 사용할 수 있는 비용 k가 입력된다. (1번 지점이 경곽이의 나라이다.)
둘재 줄에 bi(2 <= i <= n)가 차례대로 입력된다.

셋째 줄부터 n+1째 줄까지 n-1개 줄에 거쳐 a b c 공백으로 구분되어 주어진다. (a번 지점과 b번 지점이 길이 c의 간선으로 연결되었다는 의미이다.)

n+2째 줄부터 n+m+1째 줄까지 m개 줄에 걸쳐 a b 공백으로 구분되어 주어진다. (a >= 2, a번 지점에서 b만큼의 물이 초기에 있다는 의미이다.)

모든 입력값은 정수이다.

모든 입력 데이터에서 2 <= n <= 100 000, 1 <= m < n, 0 <= k <= 1 000 000 000, 1<= (물을 막는 비용) <= 10 000, 1 <= (간선의 길이) <= 100 000, 1 <= (근원지의 물의 양) <= 1000 을 만족한다.

[SubTask Info]
#1 : (10점) n <= 10
#2 : (20점) 근원지의 물의 양은 전부 1이다.
#3 : 추가 제한 조건은 없다.

Output

첫째 줄에 경곽이의 나라가 살 수 있는 최장 일수를 출력한다.

IO Example

Input

5 4 300
1 2 3 4
1 2 1
1 3 1
1 4 1
1 5 1
2 5
3 10
4 15
5 20

Output

3

설명) 2일째까지 모든 물을 막으면 (1*5+2*10+3*15+4*20)*2일= 300 이라는 비용을 전부 소진해서 더 이상 막을 수 없다. 3일째, 물이 1번 지점에 도달하면 경곽이의 나라가 끝난다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]