P9020 [USACO23JAN] Mana Collection P

## 题目背景 **注意：这个问题的时间限制是5秒，是默认的2.5倍。这个问题的内存限制是512MB，是默认值的两倍。** 贝西需要为一个非常重要的法术收集法力。贝西有 $N$ $(1\le N\le 18)$ 个法力池，其中第 $i$ 个法力池每秒可积累 $m_i$ 法力 $(1\le m_i\le 10^8)$ 。这些池子由 $M$ $(0\le M\le N \cdot (N-1))$ 条有向边 $(a_i,b_i,t_i)$ 连接，这意味着她可以在 $t_i$ 秒内从 $a_i$ 移动到 $b_i$ $(1\le a_i, b_i\le N$, $a_i\neq b_i$, $1\le t_i\le 10^9)$ 。每当贝西出现在一个池子里，她就可以收集储存在那个地方的所有法力，把它清空。在 $0$ 的时候，所有的法力池都是空的，贝西可以选择任何一个池子来开始收集。 回答 $Q$ $(1\le Q\le 2\cdot 10^5)$ 个查询，每个查询由两个整数 $s$ 和 $e$ 指定 $(1\le s\le 10^9$，$1\le e\le N)$ 。对于每个查询，如果贝西在第 $s$ 秒结束时必须在法力池 $e$ 处，请确定她在 $s$ 秒内能收集的最大法力值。

第一行包含 $N$ 和 $M$ 。 下一行包含 $m_1,m_2,\dots, m_N$ 。 接下来的 $M$ 行每行包含 $a_i,b_i,t_i$ 。在输入中没有一对有序的 $(a_i,b_i)$ 出现超过一次。 下一行包含 $Q$ 。 接下来的 $Q$ 行每行包含两个整数 $s$ 和 $e$ 。

输出 $Q$ 行，每个查询所对应的答案。

对于第一个样例： 第一次询问。贝西在 $5$ 秒后从水池 $1$ 中取出 $5$ 个法力值。 第二次查询。 $5$ 秒后，贝西从水池 $2$ 中获取 $50$ 点法力。 第三次查询。 $100$ 秒后，贝西从水池 $1$ 中获取 $100$ 法力值。 第四次查询。 $90$ 秒后贝西从水池 $1$ 中获得 $90$ 法力， $100$ 秒后从水池 $2$ 中获得 $1000$ 法力。 测试点 $3-4$: $N\le 10, Q\le 100$ 。 测试点 $5-9$: $N\le 10$ 。 测试点 $10-14$: $Q\le 100$ 。 测试点 $15-17$: $N = 16$ 。 测试点 $18-20$: $N = 17$ 。 测试点 $21-24$：没有其他约束条件 。