AT_joigsp2025_h 勇者ビ太郎 3 (Bitaro the Brave 3)

勇者ビ太郎は，モンスターから村を守る防衛戦のクエストに挑もうとしている． 防衛戦の難易度は $ 1 $ 以上 $ L $ 以下の整数で表され，この値は挑戦時に選択することができる． 難易度 $ \ell $ ( $ 1 \leqq \ell \leqq L $ ) の防衛戦では，出現するモンスターの HP が (難易度 $ 1 $ の場合を基準として) $ \ell $ 倍になる． 防衛戦は $ T $ 秒間行われ， $ N $ 体のモンスターが次々と現れる． モンスターには $ 1 $ から $ N $ までの番号が付けられている． 防衛戦が開始されてから $ t $ 秒後 ( $ 0 \leqq t \leqq T $ ) のことを，時刻 $ t $ と呼ぶ． モンスター $ i $ ( $ 1 \leqq i \leqq N $ ) は時刻 $ S_i $ ( $ 0 \leqq S_i < T $ ) に出現し， その強さは $ P_i $ で，その HP は，防衛戦の難易度を $ \ell $ として， $ \ell \times H_i $ である． 防衛戦の間，ビ太郎は以下の操作を何度でも行うことができる． - 現在出現しているモンスターの中から $ 1 $ 体を選び， $ 1 $ 秒かけてそのモンスターに攻撃する．そのモンスターの HP は $ 1 $ 減少する．HP が $ 0 $ になったモンスターは倒れ，これ以上攻撃することはできない． 時刻 $ T $ になると防衛戦は終了し，防衛戦の **評価値** が以下のように計算される． - 時刻 $ T $ の直後の時点でのモンスター $ i $ ( $ 1 \leqq i \leqq N $ ) の HP を $ h_i $ とすると，評価値は $ h_1 P_1 + h_2 P_2 + \dots + h_N P_N $ である． 評価値がクエストにより定められた基準値 $ m $ 以下であるとき，かつそのときに限り，ビ太郎はクエストを達成することができる． より高い難易度でクエストを達成するほど報酬も豪華になるため，ビ太郎は，クエストを達成することができる最大の難易度を求めたい． しかし，基準値は事前には知らされないため，ビ太郎は， $ Q $ 個の基準値の候補 $ M_1, M_2, \dots, M_Q $ について， クエストを達成することができる最大の難易度を求めることにした． 防衛戦の情報と基準値の候補の情報が与えられたとき，それぞれの基準値の候補について，クエストを達成することが可能かどうか判定し， 可能な場合は，クエストを達成することができる最大の難易度を求めるプログラムを作成せよ． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ L $ $ T $ $ S_1 $ $ H_1 $ $ P_1 $ $ S_2 $ $ H_2 $ $ P_2 $ $ \vdots $ $ S_N $ $ H_N $ $ P_N $ $ Q $ $ M_1 $ $ M_2 $ $ \vdots $ $ M_Q $

$ Q $ 行出力せよ． $ j $ 行目 ( $ 1 \leqq j \leqq Q $ ) には， $ m = M_j $ としたときの，クエストを達成することができる最大の難易度を出力せよ．どの難易度でもクエストを達成することができない場合は，代わりに `0` を出力せよ．

### 小課題 1. ( $ 5 $ 点) $ N \leqq 30 $ ， $ Q = 1 $ ， $ M_1 = 0 $ ， $ L = 1 $ ． 2. ( $ 10 $ 点) $ N \leqq 30 $ ， $ Q = 1 $ ， $ M_1 = 0 $ ． 3. ( $ 14 $ 点) $ N \leqq 30 $ ， $ Q \leqq 3 $ ． 4. ( $ 10 $ 点) $ Q \leqq 3 $ ． 5. ( $ 33 $ 点) $ N \leqq 30 $ ． 6. ( $ 7 $ 点) $ N \leqq 400 $ ． 7. ( $ 16 $ 点) $ N \leqq 1\,800 $ ． 8. ( $ 5 $ 点) 追加の制約はない． --- ### Sample Explanation 1 難易度 $ 1 $ の防衛戦では，以下のように行動することで評価値 $ 4 $ を達成することができる．評価値 $ 3 $ 以下を達成することはできない． 時刻 出来事 $ 0 $ モンスター $ 1 $ (HP $ 9 $ ) が出現する． $ 0 $ – $ 8 $ モンスター $ 1 $ に $ 8 $ 回攻撃する．モンスター $ 1 $ の HP が $ 9 $ から $ 1 $ まで減少する． $ 8 $ モンスター $ 2 $ (HP $ 5 $ ) が出現する． $ 8 $ – $ 9 $ モンスター $ 2 $ に $ 1 $ 回攻撃する．モンスター $ 2 $ の HP が $ 5 $ から $ 4 $ まで減少する． $ 9 $ – $ 10 $ モンスター $ 1 $ に $ 1 $ 回攻撃する．モンスター $ 1 $ の HP が $ 1 $ から $ 0 $ まで減少する． $ 10 $ モンスター $ 1 $ が倒れる． $ 10 $ 防衛戦が終了する．評価値は $ 0 \times P_1 + 4 \times P_2 = 4 $ となる． また，難易度 $ 2 $ の防衛戦では，以下のように行動することで評価値 $ 26 $ を達成することができる．評価値 $ 25 $ 以下を達成することはできない． 時刻 出来事 $ 0 $ モンスター $ 1 $ (HP $ 18 $ ) が出現する． $ 0 $ – $ 8 $ モンスター $ 1 $ に $ 8 $ 回攻撃する．モンスター $ 1 $ の HP が $ 18 $ から $ 10 $ まで減少する． $ 8 $ モンスター $ 2 $ (HP $ 10 $ ) が出現する． $ 8 $ – $ 10 $ モンスター $ 1 $ に $ 2 $ 回攻撃する．モンスター $ 1 $ の HP が $ 10 $ から $ 8 $ まで減少する． $ 10 $ 防衛戦が終了する．評価値は $ 8 \times P_1 + 10 \times P_2 = 26 $ となる． さらに，この入力例においては $ L = 2 $ であるため，難易度 $ 3 $ 以上の防衛戦を選択することができない．したがって，出力は以下のようになる． - $ 1 $ 個目の基準値 $ M_1 = 0 $ ではどの難易度でもクエストを達成することができないため， $ 1 $ 行目には `0` を出力する． - $ 2 $ 個目の基準値 $ M_2 = 20 $ では最大で難易度 $ 1 $ の防衛戦までクエストを達成することができるため， $ 2 $ 行目には $ 1 $ を出力する． - $ 3 $ 個目の基準値 $ M_3 = 40 $ では最大で難易度 $ 2 $ の防衛戦までクエストを達成することができるため， $ 3 $ 行目には $ 2 $ を出力する． この入力例は小課題 $ 3, 4, 5, 6, 7, 8 $ の制約を満たす． --- ### Sample Explanation 2 この入力例はすべての小課題の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 2, 3, 4, 5, 6, 7, 8 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 5, 6, 7, 8 $ の制約を満たす． --- ### Sample Explanation 5 この入力例は小課題 $ 5, 6, 7, 8 $ の制約を満たす． ### Constraints - $ 1 \leqq N \leqq 6\,000 $ ． - $ 1 \leqq L \leqq 10\,000\,000 $ ． - $ 1 \leqq T \leqq 10^{18} $ ． - $ 0 \leqq S_i < T $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq H_i $ ( $ 1 \leqq i \leqq N $ )． - $ 1 \leqq P_i $ ( $ 1 \leqq i \leqq N $ )． - $ H_1 P_1 + H_2 P_2 + \cdots + H_N P_N \leqq 10^{11} $ ． - $ 1 \leqq Q \leqq 1\,000\,000 $ ． - $ 0 \leqq M_j \leqq 10^{18} $ ( $ 1 \leqq j \leqq Q $ )． - $ M_1 < M_2 < \cdots < M_Q $ ． - 入力される値はすべて整数である．