G - 勇者ビ太郎 3 (Bitaro the Brave 3) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点： 100 点

勇者ビ太郎は，モンスターから村を守る防衛戦のクエストに挑もうとしている． 防衛戦の難易度は 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 \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．
  • 入力される値はすべて整数である．

小課題

  1. (1 点) N \leqq 30，Q = 1，M_1 = 0，L = 1．
  2. (3 点) N \leqq 30，Q = 1，M_1 = 0．
  3. (10 点) N \leqq 30，Q \leqq 3．
  4. (10 点) Q \leqq 3．
  5. (35 点) N \leqq 30．
  6. (8 点) N \leqq 400．
  7. (20 点) N \leqq 1\,800．
  8. (13 点) 追加の制約はない．

入力例 1

2 2 10
0 9 2
8 5 1
3
0
20
40

出力例 1

0
1
2

難易度 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 の制約を満たす．

入力例 2

3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0

出力例 2

0

この入力例はすべての小課題の制約を満たす．

入力例 3

3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0

出力例 3

7000000

この入力例は小課題 2, 3, 4, 5, 6, 7, 8 の制約を満たす．

入力例 4

5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500

出力例 4

6
8
10
12
13
15
16
18
19
20
20

この入力例は小課題 5, 6, 7, 8 の制約を満たす．

入力例 5

15 10000000 1000000000000
160278118759 43084 33592
442653603914 19490 23090
824219815410 50858 89563
502303340628 56629 45080
495062829942 87342 28821
234536700105 45384 34328
396080693809 78081 50812
734374391045 40873 92012
122606844331 25451 30426
204076581972 58431 13989
495156368673 54276 41670
812963939390 27614 50228
405067019838 96324 18477
464546304875 67562 45956
528559327980 41759 15546
10
216000000000000
1728000000000000
5832000000000000
13824000000000000
27000000000000000
46656000000000000
74088000000000000
110592000000000000
157464000000000000
216000000000000000

出力例 5

995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125

この入力例は小課題 5, 6, 7, 8 の制約を満たす．