Mana Collection
**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≤N≤18) mana pools, the ith of which accumulates mi mana per second (1≤mi≤108). The pools are linked by a collection of M (0≤M≤N(N−1)) directed edges (ai,bi,ti), meaning that she can travel from ai to bi in ti seconds (1≤ai,bi≤N, ai=bi, 1≤ti≤109). 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≤Q≤2⋅105) queries, each specified by two integers s and e (1≤s≤109, 1≤e≤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 sth second.
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.
An example where Bessie is able to collect much larger amounts of mana.
SCORING:
- Inputs 3-4: N≤10,Q≤100
- Inputs 5-9: N≤10
- Inputs 10-14: Q≤100
- Inputs 15-17: N=16
- Inputs 18-20: N=17
- Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
First line contains N and M.
Next line contains m1,m2,…,mN.
Next M lines contain ai,bi,ti. No ordered pair (ai,bi) 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.