시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 23 2 2 10.000%

문제

어떤 지역에서는 N 종류의 생물이 모여서 살고 있다. 이 중 두 종류의 생물 사이에 잡아먹고 먹히는 관계가 성립할 수 있는데, 잡아먹는 쪽을 포식자라고 하며 먹히는 쪽을 피식자라 한다. 이러한 관계가 여러 생물들 사이에서 이어지면 사슬과 같은 천적 관계를 형성하게 된다. 이것이 바로 먹이연쇄이다.

먹이연쇄는 "먹이"의 형태로 태양에너지가 생물의 몸속으로 차례차례 전송되어 가는 과정이다. 다른 생물이 아닌 태양에너지를 에너지원으로 삼아 무기물에서 유기물을 합성하는 생물을 생산자라고 하고, 다른 생물을 먹어 에너지원으로 삼는 생물을 소비자라고 한다.

이 지역에서는 N종류의 생물이 안정적인 먹이 사슬을 이루며 평화롭게 살고 있었지만, 최근 생산자들이 중금속에 오염되면서 생태계가 위험에 처했다. 이 생태계의 최종 소비자는 사람이기 때문에, 사람들은 생존에 위협을 느끼기 시작했고, 과연 이 오염된 생태계에서 사람이 생존해 갈 수 있는 지 궁금해 하기 시작했다.

사람들은 편의를 위해 생물들에 1~N-1까지의 번호를 붙였고, 사람은 N번 생물이다. 이 생태계에 속한 생물들은 생존을 위해 다음과 같은 조건을 따른다.
- i번 생물이 살아가기 위해선 다른 생물로부터 C[i]kcal이상의 칼로리를 섭취해야 한다. 생산자는 태양에너지로부터 에너지를 얻으므로 C[i]가 0이다.
- i번 생물에 H[i]ppm을 초과하여 중금속이 쌓이면 i번 생물은 멸종하고, 다른 생물들은 i번 생물을 먹을 수 없다.
- 먹이를 먹을 때는 필요한 칼로리를 섭취하면서도 축적되는 중금속은 가장 적어지도록 먹이를 먹는다.

i번 생물이 다른 생물에게 먹혔을 때는 일정하게 E[i]kcal의 칼로리를 낸다. 다른 생물로부터 칼로리를 섭취했다고 i번 생물의 칼로리가 높아지지는 않는다고 하자.
  그렇지만 중금속은 생산자로부터 소비자로 농축되어 가며, 포식자가 중금속을 오염된 피식자를 먹으면 피식자에 쌓여 있던 중금속은 배출되지 않고 그대로 포식자에게 쌓여 간다.
  입력에 생물의 크기가 주어지지는 않지만, 모든 생물들은 자기보다 크기가 작은 생물들만을 먹을 수 있다고 가정한다. 즉, 두 생물이 서로 천적관계에 있을 수도 없고, i번 생물이 j번 생물을 먹고 j번 생물이 k번 생물을 먹을 수 있는데, k번 생물이 다시 i번 생물을 먹는다거나 하는 일은 존재할 수 없다.
  각 종류의 생물들은 포식자가 충분히 먹고도 멸종되지 않을 정도로 충분히 많고, 포식자는 한 종류의 피식자를 여러 마리 섭취하여 필요한 칼로리를 얻을 수도 있다고 하자.

현재는 중금속 오염이 생산자에게만 진행되었고, 멸종되지 않은 생산자들은 자신이 버틸 수 있는 중금속의 최대량, 즉 H[i]만큼 중금속이 농축된 상태이다. 사람들은 이 상태로 생물농축이 계속해서 진행되었을 때 인간이 과연 멸종할 지, 멸종하지 않는다면 중금속이 체내에 얼마나 농축될지를 알고 싶다.

입력

첫째 줄에 생물 종의 수 N이 주어진다. (1≤N≤1,000) 이어서 N개의 줄에 걸쳐 세 자연수 C[i], H[i], E[i]가 주어지는 데, C[i](1≤C[i]≤10,000)는 i번 생물이 섭취해야 할 칼로리를, H[i](1≤H[i]≤10,000)는 i번 생물이 섭취할 수 있는 최대 중금속 양을, E[i]는 다른 생이 i번 생물을 먹었을 때 얻을 수 있는 칼로리를 가리킨다.

다음 줄에는 천적관계의 수 M이 주어진다. (1≤M≤10,000) 이어서 M개의 줄에 걸쳐 각 줄에 N 이하의 서로 다른 두 자연수가 "a b"의 형태로 주어지는데, 이는 a번 생물이 b번 생물에게 먹힌다는 것을 의미한다.

출력

첫째줄에 N번 생물, 즉 사람이 생존할 수 있는지를 yes나 no로 출력한다. 생존할 수 있다면 yes를, 생존할 수 없다면 no를 출력하면 된다.

만약 생존할 수 있다면 두 번째 줄에 중금속이 최소 얼마나 오염되어 있을 지를 출력한다.

예제 입력

5
0 2 3
0 3 2
3 4 3
6 6 12
12 12 4
5
1 4
2 4
2 3
4 5
3 5

예제 출력

yes
4

힌트