platinum_Mana_Collection (USACO January_Contest)
Time limit: 5 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: tsp, dynamic programming, bitmask dp, convex hull, bitmask, binary search

**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 $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.
INPUT FORMAT (input arrives from the terminal / stdin):
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$.
OUTPUT FORMAT (print output to the terminal / stdout):
$Q$ lines, one for each query.
SAMPLE INPUT:
2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2
SAMPLE OUTPUT:
5
50
100
1090
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.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
160000000
239999988050000000
119992550000000
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.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: