Description

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.

Input Format

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

Output Format

$Q$ lines, one for each query.

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

5
50
100
1090

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

160000000
239999988050000000
119992550000000

Hint

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.