30101번 - 금고 털이

GSHS국가의 수도는 $N$개의 빌딩으로 이루어져 있다. 빌딩은 일렬로 놓여 있으며, 왼쪽에서부터 $1, 2, \cdots, N$까지 번호가 붙어 있다. $i$번 빌딩의 높이는 $H_i$이다. 당신은 각 빌딩의 높이가 서로 다르다는 것을 알고 있다. 각 빌딩의 옥상에는 금고가 있다. $i$번 빌딩의 금고에는 총 $C_i$원의 돈을 포함하고 있다. $H_i$와 $C_i$는 모두 양의 정수이다.

당신은 수도의 금고들을 털어 돈을 버는 금고 털이이다. 금고 털이는 다음과 같은 규칙으로 이루어진다. 당신은 임의의 빌딩의 옥상에서 시작하여, 하나 이상의 빌딩을 오가며 빌딩의 금고를 털 것이다. 또한, 금고 털이를 마친 이후에는 $E$번 빌딩의 옥상으로 당신의 조력자가 헬리콥터를 타고 당신이 수도를 빠져나가는 것을 도와줄 것이다. 따라서 당신이 마지막으로 도착해야 하는 빌딩은 $E$번 빌딩이다. 또한, 안전상의 이유로 다음과 같은 규칙을 지켜야 한다.

1. 한 빌딩에서 다른 빌딩으로 이동할 때에는 이동하려는 빌딩이 원래 빌딩의 옥상에서 보여야 한다. 빌딩 $i$에서 빌딩 $j$가 보인다는 것은 빌딩 $i$와 $j$ 사이(빌딩 $i$, $j$ 포함)의 모든 빌딩의 높이가 빌딩 $j$의 높이보다 같거나 작다는 것이다. 그렇지 않다면 다른 빌딩에 가려져 보이지 않게 된다.
2. 너무 많은 빌딩의 금고를 털면 발각될 위험이 있으므로, 이동 과정에서 연속하게 방문한 두 빌딩의 금고는 최대 하나만 털 수 있다.
3. 모든 방문한 빌딩에 대해, 각 빌딩 $i$에서 얻은 수익은 금고를 털었을 경우 $C_i$, 그렇지 않은 경우는 0이다. 금고 털이의 총 수익은 방문한 모든 빌딩에 대한 수익의 합이다.

당신은 각 빌딩의 높이 $H_i$, 각 빌딩의 금고의 가치 $C_i$를 모두 조사했다. 빌딩의 높이는 확실하지만, 각 빌딩의 금고의 가치는 불확실할 수도 있어서 값이 바뀔 수 있다. 또한, 조력자가 도착할 빌딩의 번호 또한 바뀔 수 있다. 정보가 $Q$번 새로 갱신될 때마다, 주어진 조건에 맞게 금고를 털어서 벌 수 있는 가능한 수익의 최댓값을 구해 보자.

첫 줄에 두 정수 $N$, $E$가 공백을 사이에 두고 주어진다.

두 번째 줄에 $N$개의 정수 $H_1, H_2, \cdots, H_N$이 공백을 사이에 두고 주어진다.

세 번째 줄에 $N$개의 정수 $C_1, C_2, \cdots, C_N$이 공백을 사이에 두고 주어진다.

네 번째 줄에 정수 $Q$가 주어진다.

다섯 번째 줄부터 $Q$줄에 걸쳐 정보의 갱신이 다음 형식과 같이 주어진다.

• 1 i c: $i$번 건물의 금고 가치가 $c$원으로 변한다.
• 2 e: 조력자의 위치 $E$가 $e$로 변한다.

총 $Q+1$줄을 출력해야 한다.

첫 줄에는 초기 조건에서 주어진 조건에 맞게 금고를 털어서 벌 수 있는 최대 이익을 출력해야 한다.

$i+1$번째 줄에는 초기 조건에 $i$번째까지의 변화까지 적용했을 때 얻을 수 있는 최대 이익을 출력해야 한다. $(1 \le i \le Q)$

• $1 \le N \le 10^5$
• $1 \le E \le N$
• $1 \le H_i \le N$, $H_i$는 서로 다르다.
• $1 \le C_i \le 10^9$
• $0 \le Q \le 10^5$

금고 털이를 시작하는 위치와 $E$가 같아도 된다.