레이팅 미적용JOI 商店には N 個の商品があり,商品には 1 から N までの番号が付けられている.商品 i ( \(1 \le i \le N\) ) の定価は A i である.
JOI 商店のインターネット通販では,商品を購入するときに単一の種類のクーポンを 0 枚以上の好きな枚数だけ使用することができる.JOI 商店のクーポンは Q 種類存在し,クーポンの種類には 1 から Q までの番号が付けられている.
種類 j ( \(1 \le j \le Q\) ) のクーポンを k 枚 ( \(k \ge 0\) ) 使用したときの効果は以下の通りである.
i = 1, 2, ..., N について,商品 i の価格が max (0, A i − D j × k) になる(ここで,max (0, A i − D j × k) は 0 と A i − D j × k のうち小さくないほうを表す).
商品の価格とは別に, C j × k の追加料金がかかる.
各クーポンの種類に対応して, Q 個の質問が考えられる. j 番目の質問は以下の通りである.
種類 j のクーポンのみを使用して N 個の商品を 1 つずつ買う場合,払う合計金額の最小値は何か.
商品とクーポンの情報が与えられたとき,各質問への答えを求めるプログラムを作成せよ.
1 ≦ N ≦ 300 000 .
1 ≦ Q ≦ 300 000 .
1 ≦ A i ≦ 10 9 ( \(1 \le i \le N\) ).
1 ≦ C j ≦ 10 9 ( \(1 \le j \le Q\) ).
1 ≦ D j ≦ 10 9 ( \(1 \le j \le Q\) ).
入力される値はすべて整数である.
( 6 点) N = 1 , Q ≦ 3 000 .
( 3 点) \(N \le 100\) , \(Q \le 100\) , A i ≦ 100 ( \(1 \le i \le N\) ).
( 8 点) N ≦ 3 000 , Q ≦ 3 000 , D j = 1 ( \(1 \le j \le Q\) ).
( 22 点) N ≦ 3 000 , Q ≦ 3 000 .
( 15 点) D j = 1 ( \(1 \le j \le Q\) ).
( 18 点) A i ≦ 1 000 000 ( \(1 \le i \le N\) ).
( 28 点) 追加の制約はない.
入力は以下の形式で与えられる.
N Q
A 1 A 2 ... A N
C 1 D 1
:
C Q D Q
Q 行出力せよ. j 行目 ( \(1 \le j \le Q\) ) には, j 番目の質問への答えを出力せよ.
3 4
8 10 3
12 5
3 2
3 4
100 100
20
14
8
21
1 3
83
2 5
4 5
6 5
34
67
83
15 3
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
1 1
10 1
20 1
9
67
77
6 3
1000000000 999999999 999999998 999999997 999999996 999999995
1000000000 1
1 1000000000
900000000 900000000
5999999985
1
1499999985