Bitaro the Brave 3

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.