题目描述

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 ith 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.

输入格式

First line contains $N$ and $M$.

Next line contains $m_1,m2, \cdots ,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$.

输出格式

$Q$ lines, one for each query.

题目大意

题目背景

注意：这个问题的时间限制是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$ 行，每个查询所对应的答案。

样例 #1

样例输入 #1

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

样例输出 #1

5
50
100
1090

样例 #2

样例输入 #2

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

样例输出 #2

160000000
239999988050000000
119992550000000

提示

对于第一个样例：

第一次询问。贝西在 $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$：没有其他约束条件 。

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

提示

Explanation for Sample 1

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.

Explanation for Sample 2

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.