06710. USACO·法力收集 未做

注意：本题的时限为 5 秒，是默认时限的 2.5 倍；内存限制为 512MB，是默认限制的两倍。

Bessie 最近迷上了魔法，需要为一场十分重要的法术收集法力。Bessie 有 $N$（$1\le N\le 18$）个法力池，第 $i$ 个法力池每秒积聚 $m_i$ 点法力（$1\le m_i\le 10^8$）。法力池之间由 $M$（$0\le M\le N(N-1)$）条有向边 $(a_i,b_i,t_i)$ 相连，表示她可以在 $t_i$ 秒内从 $a_i$ 走到 $b_i$（$1\le a_i,b_i\le N$，$a_i\ne b_i$，$1\le t_i\le 10^9$）。每当 Bessie 身处某个法力池时，她可以收集该处储存的所有法力，将其清空。在时刻 $0$，所有法力池都是空的，Bessie 可以选择任意一个法力池作为起点。

回答 $Q$（$1\le Q\le 2\cdot 10^5$）个询问，每个询问由两个整数 $s$ 和 $e$（$1\le s\le 10^9$，$1\le e\le N$）给出。对于每个询问，求出：如果 Bessie 必须在第 $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$ 行，每个询问一行。

【样例解释】

这是 Bessie 能够收集到多得多的法力的一个例子。

【数据规模与约定】

• 测试点 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：无附加限制。