시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 (추가 시간 없음) 1024 MB 84 16 7 9.589%

문제

화학과 대학원생 탐레프는 S, U, N 원자로 이루어진 분자를 만드려고 한다. 레프는 이미 분자 구조를 결정했다. 레프의 분자 구조는 원자를 정점으로 하고, 두 원자의 결합을 간선으로 했을 때 특이한 선인장 그래프를 이룬다. 특이한 선인장 그래프란, 모든 정점이 하나 이하의 단순 사이클에만 포함되는 그래프를 말한다.

아직 레프는 어떤 위치에 어떤 원자를 채울지 결정하지 않았다. 레프는 같은 종류의 두 원자를 결합시키는 방법을 모르기 때문에 결합된 두 원자가 같은 종류이면 안 된다. 각각의 위치에 S, U, N 원자를 두기 위해 필요한 에너지가 각각 주어질 때, 레프는 가장 안정한 분자를 만드려고 한다. 가장 안정한 분자는 모든 위치에 대해 필요한 에너지의 합이 가장 낮은 분자를 말한다.

레프는 실험을 통해 어떤 위치에 어떤 원자를 두기 위해 필요한 에너지를 계속해서 수정해나간다. 필요한 에너지가 수정될 때마다 레프에게 만들 수 있는 가장 안정한 분자를 알려주자.

입력

1번째 줄에 분자 구조 내의 원자 수 N, 결합 수 M, 레프가 실험을 하는 횟수 Q가 공백으로 구분되어 주어진다.

i + 1번째 줄부터 N개의 줄에 분자 구조의 i번째 위치에 S, U, N 원자를 두기 위해 필요한 에너지 Si, Ui, Ni가 각각 공백으로 구분되어 주어진다. (1 ≤ i ≤ N)

i + N + 1번째 줄부터 M개의 줄에 i번째 결합이 연결하는 두 원자 위치의 번호가 공백으로 구분되어 주어진다. (1 ≤ i ≤ M)

i + N + M + 1번째 줄부터 Q개의 줄에 i번째 실험의 결과를 나타내는 두 정수 Ai, Bi, Ci가 공백으로 구분되어 주어진다. (1 ≤ i ≤ Q) 이는 Ai번 위치에 Bi 원자를 두는데 필요한 에너지를 Ci로 수정한다는 의미이다. 참고로 Bi가 1인 경우 S, 2인 경우 U, 3인 경우 N 원자를 의미한다.

출력

Q줄에 걸쳐 필요한 에너지가 수정될 때마다 만들 수 있는 가장 안정한 분자를 만드는데 필요한 에너지의 합을 한 줄에 하나씩 출력한다.

제한

  • 1 ≤ N ≤ 100,000
  • M ≥ N - 1
  • 1 ≤ Q ≤ 100,000
  • 1 ≤ Si, Ui, Ni ≤ 104 (1 ≤ i ≤ N)
  • 주어지는 분자 구조가 이루는 그래프는 단순 그래프이다.
  • 주어지는 분자 구조가 이루는 그래프는 연결 그래프이다.
  • 주어지는 분자 구조가 이루는 그래프에서 모든 정점은 하나 이하의 단순 사이클에만 포함된다.
  • 1 ≤ Ai ≤ N, 1 ≤ Bi ≤ 3, 1 ≤ Ci ≤ 104 (1 ≤ i ≤ Q)

예제 입력 1

6 7 3
50 70 90
50 70 90
50 70 90
50 70 90
50 70 90
50 70 90
1 2
6 4
1 5
4 3
3 6
5 4
5 2
5 2 4
3 2 27
4 2 51

예제 출력 1

354
311
311

출처

Contest > IDTcup > 제 2회 IDTcup F번