{"raw_statement":[{"iden":"statement","content":"**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.**\n\nBessie 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.\n\nAnswer $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. "},{"iden":"input","content":"First line contains $N$ and $M$.\n\nNext line contains $m_1,m2, \\cdots ,m_N$.\n\nNext $M$ lines contain $a_i,b_i,t_i$. No ordered pair $(a_i,b_i)$ appears more than once in the input.\n\nNext line contains $Q$.\n\nNext $Q$ lines contain two integers $s$ and $e$. "},{"iden":"output","content":"$Q$ lines, one for each query. "},{"iden":"note","content":"### Explanation for Sample 1\n\nFirst query: Bessie takes $5$ mana from pool $1$ after $5$ seconds.\n\nSecond query: Bessie takes $50$ mana from pool $2$ after $5$ seconds.\n\nThird query: Bessie takes $100$ mana from pool $1$ after $100$ seconds.\n\nFourth query: Bessie takes $90$ mana from pool $1$ after $90$ seconds and $1000$ mana from pool $2$ after $100$ seconds. \n\n### Explanation for Sample 2\n\nAn example where Bessie is able to collect much larger amounts of mana. \n\n### Scoring\n\n - Inputs $3-4$: $N \\le 10$,$Q \\le 100$\n - Inputs $5-9$: $N \\le 10$\n - Inputs $10-14$: $Q \\le 100$\n - Inputs $15-17$: $N=16$\n - Inputs $18-20$: $N=17$\n - Inputs $21-24$: No additional constraints."}],"translated_statement":null,"sample_group":[["2 1\n1 10\n1 2 10\n4\n5 1\n5 2\n100 1\n100 2","5\n50\n100\n1090"],["4 8\n50000000 100000000 20000000 70000000\n1 2 20\n2 1 50\n2 3 90\n1 3 40\n3 1 10\n4 1 25\n1 4 5\n4 3 70\n3\n8 3\n1000000000 1\n500000 4","160000000\n239999988050000000\n119992550000000"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}