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 there, emptying it. At time $0$, all mana pools are empty, and Bessie can start at any pool.

Answer $Q$ ($1\le Q\le 2\cdot 10^5$) queries. Each query gives two integers $s$ and $e$ ($1\le s\le 10^9$, $1\le e\le N$). For each query, find 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.

The first line contains $N$ and $M$.

The next line contains $m_1, m_2, \dots, m_N$.

The next $M$ lines each contain $a_i$, $b_i$, $t_i$. No ordered pair $(a_i,b_i)$ appears more than once.

The next line contains $Q$.

The next $Q$ lines each contain two integers $s$ and $e$.

Print $Q$ lines, one for each query.