저항

다가올 대회를 앞두고 몇몇 참가자가 „저항“ 게임을 하려고 모였다. 이번에는 규칙을 바꾸기로 했다. 이번에도 „선한“ 진영과 „악한“ 진영이 있지만, 각 진영의 인원수는 고정되어 있지 않다. 모든 참가자마다 두 값이 주어진다. 선한 진영에 합류했을 때의 기여도와 악한 진영에 합류했을 때의 기여도이다. 또한 일부 참가자 쌍에 대해서는 두 사람 사이의 우정 값이 주어진다. 두 친구가 서로 다른 진영에 속하면 그 게임에서 둘의 우정은 „깨진“ 것으로 본다. 흥미로운 사실이 하나 있는데, 전체 참가자의 일부이면서 공집합이 아닌 임의의 그룹에 대해, 그 그룹에 속한 사람과 그룹 밖의 사람 사이에 우정이 적어도 하나 존재한다.

여기에 새 규칙이 하나 더 있다. 게임이 시작되기 전에 사람들을 두 진영으로 나눈다. 물론 모든 참가자는 그 분배를 Deni가 하기로 했다. Deni는 분배의 가치가 최대가 되게 하려 한다. 어떤 분배의 가치는 각 참가자가 자신이 합류한 진영에 기여하는 값을 모두 더하고, „깨진“ 우정의 값을 빼서 계산한다. Deni는 여러분의 도움이 필요하다. 최대 분배의 가치를 구하는 프로그램을 작성하시오.

그런데 이게 전부가 아니다. 시간이 지나면 그룹에 있던 일부 사람이 떠난다. 또 어느 시점에는 떠났던 사람 중 일부가 돌아오고, 이런 일이 반복된다. 즉 새로운 게임마다 분배를 다시 계산해야 한다. 변화는 다음과 같다. 처음에는 그룹의 참가자 N명이 모두 있다. 그다음부터 다음 변화가 주어진다. 타입 2 변화는 어떤 참가자가 떠나는 것이고, 타입 1 변화는 당시에 없던 어떤 참가자가 돌아오는 것이다. 타입 3 변화는 당시에 없던 모든 참가자가 돌아오는 것이고, 타입 4 변화는 1번부터 $\lfloor N/5 \rfloor$번까지의 참가자가 떠나는 것이다(이는 N을 5로 나눈 몫이다). 이제 Deni의 문제는 훨씬 어려워진다.

표준 입력의 첫 줄에서 두 양의 정수 N과 M을 읽는다. N은 참가자의 수, M은 알려진 우정의 수이다. 표준 입력의 둘째 줄에서 N개의 수를 읽는다. 각 참가자가 선한 진영에 기여하는 값이다(첫 번째 수는 첫 번째 참가자, 두 번째 수는 두 번째 참가자, 이런 식이다). 표준 입력의 셋째 줄에서 N개의 수를 읽는다. 각 참가자가 악한 진영에 기여하는 값이다(첫 번째 수는 첫 번째 참가자, 두 번째 수는 두 번째 참가자, 이런 식이다). 다음 M개 줄에서 세 수 x, y, t를 읽는다. 이는 번호가 x인 참가자와 y인 참가자 사이의 우정 값이 t라는 뜻이다(참가자는 1번부터 N번까지 번호가 매겨진다). 그다음 줄에서 Q를 읽는다. Q는 변화의 수이다. 마지막 Q개 줄에서 변화를 읽는다. 변화가 타입 3 또는 4이면 그 줄에는 수가 하나만 있고, 각각 3 또는 4이다. 변화가 타입 1 또는 2이면 수가 두 개 있고, 각각 타입(= 1 또는 2)과 참가자 번호 x이다.

첫 줄에 N명의 참가자가 모두 게임에 있을 때의 최대 분배 가치를 출력한다. 타입 1과 타입 2의 변화마다, 그 변화 이후의 현재 참가자들에 대한 최대 분배 가치를 한 줄에 하나씩 출력한다.

• 2 ≤ N ≤ 103
• 1 ≤ M ≤ 105
• 0 ≤ Q ≤ 1.5×103
• 진영에 대한 모든 기여도와 모든 우정 값은 0부터 1000까지의 정수이다.

모든 참가자가 있을 때, 세 번째 참가자가 선한 진영에 있고 나머지가 다른 진영에 있을 때 분배가 최대가 된다. 이 분배에서 게임의 가치는 10+14+22+25+31- 2=100이다(참가자 1번과 3번이 서로 다른 진영에 있으므로 2를 뺀다).

타입 3 변화 후에는 모든 참가자가 있고, 그다음 타입 4 변화 후에는 1번부터 $\lfloor N/5 \rfloor$번까지의 참가자가 게임에서 떠나지만, 이 경우에는 1번 참가자만 떠난다.