| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 1024 MB | 30 | 19 | 18 | 78.261% |
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.
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$.
$Q$ lines, one for each query.
2 1 1 10 1 2 10 4 5 1 5 2 100 1 100 2
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.
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
An example where Bessie is able to collect much larger amounts of mana.