問題文

横に長いベンチが 1 つあります。 ベンチには 1 から L までの整数が割り当てられた L 個のクッションが一列に並べて置かれており、各 i (1\leq i\leq L-1) についてクッション i とクッション i+1 が隣り合っています。

このベンチに人の集団が、N 個のグループに分かれて順に座りに来ます。 j 番目のグループは A_j 人の人からなり、ベンチの隣り合う A_j 個のクッション（より厳密には、ある p について、クッション p,p+1,\dots,p+A_j-1）に 1 人ずつ座るようにします。 隣り合う A_j 個のクッションでそのすべてに人が座っていないものが存在しないとき、そのグループは座るのに 失敗 します。 座るのに 失敗 したグループがあったとき、それよりあとのグループはベンチに座りに来るのを諦めます。

1 番目のグループがベンチに座りに来る前に、KowerKoint 君は、お金を使ってグループの人数を増減させることができます。 具体的には、以下の操作を任意の回数（0 回でも良い）行います。

• B_j 円支払い、j 番目のグループの人数を 1 人減らす (j 番目のグループの人数が 2 人以上のときのみ行える）
• C_j 円支払い、j 番目のグループの人数を 1 人増やす

ただし、操作の途中や操作後に所持金が負になってはいけません。 また、B_j は負であることがあり、-x 円支払うとは x 円受け取るということを表します。

各グループが座る場所をどのように選んでも最終的に合計 y 人以上が必ず座れるような最大の y を考えます。 KowerKoint 君は、このような y を操作によって最大化したいです。 整数 Q と非負整数の列 M_1,M_2,\dots,M_Q が与えられるので、各 k (1\leq k\leq Q) について、操作前の所持金が M_k 円であるときの y の最大値を答えてください。

制約

• 1 \leq N \leq L \leq 3{,}000
• 1 \leq A_j \leq L
• -10^{9} \leq B_j \leq 10^{9}
• 0 \leq C_j \leq 10^{9}
• 1 \leq B_j+C_j
• 1 \leq Q \leq 200{,}000
• 0 \leq M_k \leq 10^{15}
• 入力はすべて整数

小課題

1. (1 点) B_j=1,C_j=1,Q=1,M_k=0
2. (99 点) 追加の制約はない

入力例 1

3 7
2 5 2
4 1 2
2 3 0
4
0
1
5
10

出力例 1

2
5
6
7

• 1 番目のクエリでは、KowerKoint 君は 0 円持っています。操作をしない場合、1 番目のグループの 2 人のみ必ず座ることができます。3 番目のグループの人数を好きなだけ増やすことができますが、増やしても必ず座れる人数は増えません。
• 2 番目のクエリでは、KowerKoint 君は 1 円持っています。1 円支払って 2 番目のグループの人数を 1 人減らすと、2 グループ目までの 2+3=5 人が必ず座ることができ、これが最大です。
• 3 番目のクエリでは、KowerKoint 君は 5 円持っています。1 円支払って 2 番目のグループの人数を 1 人減らし、3 円支払って 3 番目のグループの人数を 1 人減らすと、2+3+1=6 人すべてが必ず座ることができ、これが最大です。
• 4 番目のクエリでは、KowerKoint 君は 10 円持っています。2\times5=10 円支払って 1 番目のグループの人数を 5 人増やすと、1 番目のグループの 7 人が必ず座ることができ、これが最大です。

このテストケースは小課題 1 の制約を満たしません。

入力例 2

3 8
2 1 1
3 1 1
2 1 1
1
0

出力例 2

5

このテストケースは小課題 1 の制約を満たします。

入力例 3

7 20
3 1 4
2 -2 7
4 1 1
1 -3 8
9 2 4
6 3 1
4 -2 5
6
8
0
3
10
17
2

出力例 3

13
12
13
14
15
12

このテストケースは小課題 1 の条件を満たしません。