AT_oupc2023_day1_n Bench

横に長いベンチが $ 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 $ の最大値を答えてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ L $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ \vdots $ $ A_N $ $ B_N $ $ C_N $ $ Q $ $ M_1 $ $ M_2 $ $ \vdots $ $ M_Q $

$ Q $ 行出力してください。 $ k $ 行目には、操作前の所持金が $ M_k $ 円であるとき、KowerKoint 君の操作によって、座り方によらず必ず座れる人数の最大値を出力してください。

### 小課題 1. ( $ 1 $ 点) $ B_j=1,C_j=1,Q=1,M_k=0 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 - $ 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 の制約を満たしません。 ### Sample Explanation 2 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 3 このテストケースは小課題 1 の条件を満たしません。 ### Constraints - $ 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} $ - 入力はすべて整数