시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 2048 MB922100.000%

문제

Bitaro, the brave hero, is about to take on the Defense Battle quest to protect the village from monsters. The difficulty of the Defense Battle is represented by an integer between $1$ and $L$, inclusive, and this value can be chosen at the start of the challenge. In a Defense Battle of difficulty $ℓ$ ($1 ≤ ℓ ≤ L$), the HP of monsters is multiplied by $ℓ$ compared to that at difficulty $1$.

The Defense Battle lasts for $T$ seconds, and $N$ monsters will appear throughout the battle. Each monster is assigned a unique number from $1$ to $N$. Time $t$ ($0 ≤ t ≤ T$) refers to the moment $t$ seconds after the battle starts. Monster $i$ ($1 ≤ i ≤ N$) appears at time $S_i$ ($0 ≤ S_i < T$), has strength $P_i$, and its HP at difficulty $ℓ$ is given by $ℓ \times H_i$.

During the Defense Battle, Bitaro can perform the following action any number of times.

  • Select one of the monsters currently present and attack it, which takes $1$ second. The monster’s HP decreases by $1$. Once a monster’s HP reaches $0$, it is considered defeated and will no longer be attacked.

When time reaches $T$, the Defense Battle ends, and the penalty score is computed as follows.

  • Let $h_i$ be the HP of monster $i$ ($1 ≤ i ≤ N$) immediately after time $T$. The penalty score is computed as $h_1P_1 + h_2P_2 + \cdots + h_NP_N$.

If the penalty score is less than or equal to a threshold value $m$ specified by the quest, Bitaro successfully completes the quest.

Since higher difficulties yield better rewards, Bitaro wants to determine the highest difficulty level at which he can complete the quest. However, the threshold value is unknown in advance. Thus, Bitaro decides to determine the highest difficulty level at which he can complete the quest for each of $Q$ candidate threshold values $M_1, M_2, \dots , M_Q$.

Given the information about the Defense Battle and the candidate threshold values, write a program that determines whether the quest can be completed for each threshold value and, if possible, finds the maximum difficulty level at which the quest can be completed.

입력

Read the following data from the standard input.

$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$

출력

Write $Q$ lines to the standard output. In the $j$-th line ($1 ≤ j ≤ Q$), output the maximum difficulty level at which the quest can be completed when $m = M_j$. If the quest cannot be completed at any difficulty level, output 0 instead.

제한

  • $1 ≤ N ≤ 6\, 000$.
  • $1 ≤ L ≤ 10\, 000\, 000$.
  • $1 ≤ T ≤ 10^{18}$.
  • $0 ≤ S_i < T$ ($1 ≤ i ≤ N$).
  • $1 ≤ H_i$ ($1 ≤ i ≤ N$).
  • $1 ≤ P_i$ ($1 ≤ i ≤ N$).
  • $H_1P_1 + H_2P_2 + \cdots + H_NP_N ≤ 10^{11}$.
  • $1 ≤ Q ≤ 1\, 000\, 000$.
  • $0 ≤ M_j ≤ 10^{18}$ ($1 ≤ j ≤ Q$).
  • $M_1 < M_2 < \cdots < M_Q$.
  • Given values are all integers.

서브태스크

번호배점제한
11

$N ≤ 30$, $Q = 1$, $M_1 = 0$, $L = 1$.

23

$N ≤ 30$, $Q = 1$, $M_1 = 0$.

310

$N ≤ 30$, $Q ≤ 3$.

410

$Q ≤ 3$.

535

$N ≤ 30$.

68

$N ≤ 400$.

720

$N ≤ 1\,800$.

813

No additional constraints.

예제 입력 1

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

예제 출력 1

0
1
2

In the Defense Battle of difficulty $1$, the following actions can be taken to achieve a penalty score of $4$. It is not possible to achieve a penalty score of $3$ or lower.

Time Event
$0$ Monster $1$ (HP $9$) appears.
$0$ – $8$ Attack Monster $1$ a total of $8$ times. Monster $1$’s HP decreases from $9$ to $1$.
$8$ Monster $2$ (HP $5$) appears.
$8$ – $9$ Attack Monster $2$ once. Monster $2$’s HP decreases from $5$ to $4$.
$9$ – $10$ Attack Monster $1$ once. Monster $1$’s HP decreases from $1$ to $0$.
$10$ Monster $1$ is defeated.
$10$ The Defense Battle ends. The penalty score is $0 \times P_1 + 4 \times P_2 = 4$.

Additionally, in the Defense Battle of difficulty $2$, the following actions can be taken to achieve a penalty score of $26$. It is not possible to achieve a penalty score of $25$ or lower.

Time Event
$0$ Monster $1$ (HP $18$) appears.
$0$ – $8$ Attack Monster $1$ a total of $8$ times. Monster $1$’s HP decreases from $18$ to $10$.
$8$ Monster $2$ (HP $10$) appears.
$8$ – $10$ Attack Monster $1$ a total of $2$ times. Monster $1$’s HP decreases from $10$ to $8$.
$10$ The Defense Battle ends. The penalty score is $8 \times P_1 + 10 \times P_2 = 26$.

Furthermore, in this input example, since $L = 2$, it is not possible to choose a Defense Battle of difficulty $3$ or higher. Therefore, the output will be as follows:

  • For the first threshold value $M_1 = 0$, it is not possible to complete the quest at any difficulty, so output 0 on the first line.
  • For the second threshold value $M_2 = 20$, it is possible to complete the quest at most at difficulty $1$, so output $1$ on the second line.
  • For the third threshold value $M_3 = 40$, it is possible to complete the quest at most at difficulty $2$, so output $2$ on the third line.

This sample input satisfies the constraints of subtasks 3, 4, 5, 6, 7, and 8.

예제 입력 2

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

예제 출력 2

0

This sample input satisfies the constraints of all subtasks.

예제 입력 3

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

예제 출력 3

7000000

This sample input satisfies the constraints of subtasks 2, 3, 4, 5, 6, 7, and 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

This sample input satisfies the constraints of subtasks 5, 6, 7, and 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

This sample input satisfies the constraints of subtasks 5, 6, 7, and 8.

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.