24236번 - 1차원 애니팡

문제

1차원 세계에는 1차원 애니팡이라는 게임이 존재한다. 1차원 세계에 사는 스피드 게이머 무지는 이 게임을 최대한 빠르게 클리어하고 싶다.

게임은 초기에 첫 번째 라운드의 정수 블록 $N$개가 1차원 배열의 형태로 주어진다. 이 정수 블록들이 다음과 같은 상태이면 해당 라운드가 클리어 된다.

어떤 인접한 블록에 대해서도 부호가 같은 경우가 없다. 양수, 0, 음수는 서로 다른 부호를 갖는다.

즉 1ドル \le i < N$ 인 $i$에 대해 $A_{i} > 0 \;\And\; A_{i+1} > 0$ 이거나 $A_{i} < 0 \; \And \;A_{i+1} < 0$ 이거나 $A_{i} = 0 \;\And\; A_{i+1} = 0$인 경우가 없다.

무지가 블록에 대해서 할 수 있는 연산은 다음과 같다.

1. $i$ 번째 블록의 값 $A_{i}$에 $-1$을 곱한다. 이 연산은 $R$초가 소요된다.
2. $i$ 번째 블록의 값 $A_{i}$를 1만큼 증가시키거나 감소시킨다. 이 연산은 $C$초가 소요된다.

연산은 같은 블록에 대해서도 여러 번 수행할 수 있다.

$T+1$ 개의 라운드를 클리어해야 하며 두 번째 라운드부터는 각 라운드의 시작마다 이전 라운드의 초기 상태에서 $K$ 번째 블록의 값이 $V$로 바뀐다. (이전 라운드의 클리어 상태가 아닌 초기 상태임에 유의하자)

이때 각 라운드에 대해 클리어하기 위한 최소 시간을 구하자.

입력

입력의 첫 줄에 양의 정수 $N,ドル $R,ドル $C,ドル $T$ 가 차례대로 주어진다. 각각 블록의 수, 1번 연산의 비용, 2번 연산의 비용, 블록의 값이 바뀌는 횟수를 나타낸다. (1ドル \le $ $N,ドル $R,ドル $C,ドル $T$ $\le 100,000$)

두 번째 줄에 첫 번째 라운드의 $N$개의 정수 블록을 나타내는 수열 $A_{1}, ..., A_{N}$이 차례대로 주어진다. ($-10,000 \le $ $A_{i}$ $ \le 10,000$)

세 번째 줄부터 $T+2$ 줄까지 이전 라운드의 초기 상태에서 $K$번째 블록의 값을 $V$로 바꾸는 것을 의미하는 정수 $K, V$ 가 주어진다. (1ドル \le K $ $\le N,ドル $-10,000\le$ $V$ $\le 10,000$)

출력

각 줄마다 첫번째 라운드부터 $T+1$ 라운드까지의 클리어 최소 시간을 차례대로 출력하자.

제한

힌트