题目描述

题目译自 USACO 2023 January Contest, Platinum Problem 2. Mana Collection

Bessie 最近对魔法产生了兴趣，并且为了一个非常重要的咒语收集法力。Bessie 有 $N$ 个法力池，第 $i$ 个池子每秒可以收集 $m_i$ 单位的法力。这些池子被一组 $M$ 条有向边 $(a_i,b_i,t_i)$ 相连，表示她可以在 $t_i$ 秒内从 $a_i$ 到 $b_i$。Bessie 无论何时出现在一个池子处，她都可以收集那个池子中所有的法力，也就是清空它。在时刻 $0$，所有的法力池都是空的，并且 Bessie 可以选择任意的法力池作为起点。

回答 $Q$ 个询问，每个询问用两个整数 $s$ 和 $e$ 表示。对于每个询问，确定如果 Bessie 在第 $s$ 秒结尾必须在池子 $e$ 处的情况下，她所能收集到的最多法力值是多少。

输入格式

第一行两个整数 $N\ (1\le N\le 18)$ 和 $M\ (0\le M\le N(N-1))$。

接下来一行为 $m_1,m_2,\ldots,m_N\ (1\le m_i\le 10^8)$。

接下来 $M$ 行，每行三个整数 $a_i,b_i,t_i\ (1\le a_i,b_i\le N,a_i\neq b_i,1\le t_i\le 10^9)$。输入中没有有序数对 $(a_i,b_i)$ 会出现超过一次。

接下来一行一个整数 $Q\ (1\le Q\le 2\cdot 10^5)$。

接下来 $Q$ 行，每行两个整数 $s\ (1\le s\le 10^9)$ 和 $e\ (1\le e\le N)$。

输出格式

输出 $Q$ 行，表示对询问的回答。

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

5
50
100
1090

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

160000000
239999988050000000
119992550000000

数据范围与提示

• 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 组数据：无附加限制