27553번 - Mana Collection 다국어

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 $i$th 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,m_2,\dots, 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.