この問題は Python の想定解がTLEすることを確認しています。高速な言語へ変換することをお勧めします。
shogo314君はアルバイトの計画を立てており、給料の合計を最大化しようと考えています。 しかしながら、アルバイトの雇い主は大変気まぐれなので、給料を何度も変更してきます。 変更の度に再計算するのは大変なので代わりに計算してあげてください。
$N$ 日間のアルバイトの募集があります。 出勤する日は、$2$ 日以上連続にならないように自由に選ぶことができます。
現在、$i$ 日目に出勤すると給料が $A_i$ 円得られる予定です。
以下の $Q$ 個のクエリを順番に処理してください。
ただし、クエリによる変更はそれ以降のクエリにも引き継がれます。
入力は以下の形式で標準入力から与えられます。
$N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $k_1$ $x_1$ $k_2$ $x_2$ $\vdots$ $k_Q$ $x_Q$
$Q$ 行出力してください。$i$ 行目には $i$ 個目のクエリの答えを出力してください。
3 2 8000 2000 3000 1 2000 2 10000
5000 10000
$1$ 個目のクエリの変更により、$1,2,3$ 日目に得られる予定の給料はそれぞれ $2000, 2000, 3000$ 円になります。 $1$ 日目と $3$ 日目に出勤すると $5000$ 円得られます。
$2$ 個目のクエリの変更により、$1,2,3$ 日目に得られる予定の給料はそれぞれ $2000, 10000, 3000$ 円になります。 $2$ 日目に出勤すると $10000$ 円得られます。