#arc066d. [arc066_d]Contest with Drinks Hard

[arc066_d]Contest with Drinks Hard

問題文

joisinoお姉ちゃんは、あるプログラミングコンテストの決勝を控えています。 このコンテストでは、NN 問の問題が用意されており、それらには 1N1~N の番号がついています。 joisinoお姉ちゃんは、問題 i(1iN)i(1≦i≦N) を解くのにかかる時間が TiT_i 秒であることを知っています。

このコンテストでは、コンテスタントはまず最初に、これから解く問題をいくつか選びます。 次にそれらの問題を解き、すべて解き終わると、スコアの計算が行われます。 このコンテストでのスコアの計算方法は特殊であり、具体的には、以下の式で計算されます。

  • スコア \= 「整数の組 L,R(1LRN)L,R(1≦L≦R≦N) であって、LiRL≦i≦R を満たす全ての ii について、問題 ii が解かれているようなもの」の個数 問題を解くのに要した時間の合計

なお、問題を 11 つも解かないことも許され、その際のスコアは 00 になります。

また、このコンテストでは、MM 種類のドリンクが提供されており、1M1~M の番号がついています。 そして、ドリンク i(1iM)i(1≦i≦M) を飲むと、脳が刺激され、問題 PiP_i を解くのにかかる時間が XiX_i 秒になります。 なお、XiX_i が、もともと問題 PiP_i を解くのに要する時間より長いこともありえます。 他の問題を解くのにかかる時間に変化はありません。

コンテスタントは、コンテスト開始前にいずれかのドリンクを 11 本だけ飲むことができます。 そこでjoisinoお姉ちゃんは、それぞれのドリンクについて、それを飲んだ際に、コンテストで取ることのできる最大スコアを知りたいと思いました。 あなたの仕事は、joisinoお姉ちゃんの代わりにこれを求めるプログラムを作成することです。

制約

  • 入力は全て整数である
  • 1N3\*1051≦N≦3\*10^5
  • 1Ti1091≦T_i≦10^9
  • TiT_i の総和 1012≦10^{12}
  • 1M3\*1051≦M≦3\*10^5
  • 1PiN1≦P_i≦N
  • 1Xi1091≦X_i≦10^9

入力

入力は以下の形式で標準入力から与えられる。

NN T1T_1 T2T_2 ...... TNT_N MM P1P_1 X1X_1 P2P_2 X2X_2 :: PMP_M XMX_M

出力

それぞれのドリンクについて、それを飲んだ際の最大スコアを求め、順番に 11 行ずつ出力せよ。


入力例 1

5
1 1 4 1 1
2
3 2
3 10

出力例 1

9
2

11 番目のドリンクを飲んだ場合、全ての問題を解くことで最大スコアが得られます。

22 番目のドリンクを飲んだ場合、1,2,4,51,2,4,5 番目の問題を解くことで最大スコアが得られます。


入力例 2

12
1 2 1 3 4 1 2 1 12 3 12 12
10
9 3
11 1
5 35
6 15
12 1
1 9
4 3
10 2
5 1
7 6

出力例 2

34
35
5
11
35
17
25
26
28
21