P9020 [USACO23JAN] Mana Collection P

**Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default.** Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has $N(1 \le N \le 18)$ mana pools, the ith of which accumulates $m_i$ mana per second $(1 \le m_i \le 10^8)$. The pools are linked by a collection of $M (0 \le M \le N(N−1))$ directed edges $(a_i,b_i,t_i)$, meaning that she can travel from $a_i$ to $b_i$ in $t_i$ seconds $(1 \le a_i,b_i \le N, a_i \neq b_i, 1 \le t_i \le 10^9)$. Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time $0$, all mana pools are empty, and Bessie can select any pool to start at. Answer $Q(1 \le Q \le 2 \cdot 10^5)$ queries, each specified by two integers $s$ and $e (1 \le s \le 10^9, 1 \le e \le N)$. For each query, determine the maximum amount of mana Bessie can collect in s seconds if she must be at mana pool $e$ at the end of the $s$-th second.

First line contains $N$ and $M$. Next line contains $m_1,m2, \cdots ,m_N$. Next $M$ lines contain $a_i,b_i,t_i$. No ordered pair $(a_i,b_i)$ appears more than once in the input. Next line contains $Q$. Next $Q$ lines contain two integers $s$ and $e$.

$Q$ lines, one for each query.

### Explanation for Sample 1 First query: Bessie takes $5$ mana from pool $1$ after $5$ seconds. Second query: Bessie takes $50$ mana from pool $2$ after $5$ seconds. Third query: Bessie takes $100$ mana from pool $1$ after $100$ seconds. Fourth query: Bessie takes $90$ mana from pool $1$ after $90$ seconds and $1000$ mana from pool $2$ after $100$ seconds. ### Explanation for Sample 2 An example where Bessie is able to collect much larger amounts of mana. ### Scoring - Inputs $3-4$: $N \le 10$,$Q \le 100$ - Inputs $5-9$: $N \le 10$ - Inputs $10-14$: $Q \le 100$ - Inputs $15-17$: $N=16$ - Inputs $18-20$: $N=17$ - Inputs $21-24$: No additional constraints.