Magical Mana Collection

Bessie has recently taken an interest in magic and must collect mana for a very important spell. She has N mana pools (numbered 1 through N), where the i‑th pool produces mana at a constant rate of \(m_i\) per second. The pools are connected by M directed edges. An edge \((a_i,b_i,t_i)\) means that Bessie can travel from pool a_i to pool b_i in \(t_i\) seconds.

Whenever Bessie is present at a pool, she may instantly collect all of the mana stored there, which resets that pool to 0 (after which it continues to accumulate mana at the same rate). At time \(0\) all pools are empty, and Bessie may start at any pool.

You are given \(Q\) queries. In each query, you are given two integers \(s\) and \(e\). The query asks: if Bessie must finish at mana pool \(e\) at the end of \(s\) seconds, what is the maximum mana she can possibly collect?

Note: The time limit for this problem is 5 seconds (2.5 times the default) and the memory limit is 512MB (twice the default).

Hint: Because the mana in each pool accumulates linearly with time, it is always best to postpone collection at the pool where you will wait the longest. In fact, an optimal strategy is to choose a pool \(p\) (the "farming pool") at which to wait until almost the very end. Bessie then must travel from \(p\) to the designated ending pool \(e\) within the remaining time. However, Bessie is free to choose any starting pool and the travel might be along a route that uses several edges. One useful observation is that if the chosen farming pool has production rate \(m_p\) and the minimal travel time from pool \(p\) to \(e\) along a route that does not enter any pool with a rate higher than \(m_p\) is \(d_{p,e}\), then her total collection is at least \[ m_p\times (s - d_{p,e}). \] Thus, the answer to a query is the maximum of \(m_p\times (s-d_{p,e})\) over all pools \(p\) for which a valid route from \(p\) to \(e\) exists and \(s \ge d_{p,e}\).

You are to compute \(d_{p,e}\) for each pool \(p\) and every destination \(e\). For a fixed pool \(p\), note that Bessie can only use pools with production rate \(\le m_p\) (since encountering a pool with a higher rate would enable a better farming pool, so she would rather farm there). This observation allows a separate shortest–path computation for each potential farming pool.

Good luck!

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) \((1 \le N \le 18,\; 0 \le M \le N(N-1),\; 1 \le Q \le 2\cdot10^5)\): the number of mana pools, the number of directed edges, and the number of queries.

The second line contains \(N\) integers \(m_1, m_2, \ldots, m_N\) \((1 \le m_i \le 10^8)\) where \(m_i\) is the mana production rate of pool \(i\) (mana per second).

Then \(M\) lines follow. Each line contains three integers \(a_i\), \(b_i\), and \(t_i\) \((1 \le a_i, b_i \le N,\; a_i \neq b_i,\; 1 \le t_i \le 10^9)\), meaning Bessie can travel from pool \(a_i\) to pool \(b_i\) in \(t_i\) seconds.

Finally, \(Q\) lines follow. Each query is given by two integers \(s\) and \(e\) \((1 \le s \le 10^9,\; 1 \le e \le N)\): the total time available (in seconds) and the ending pool.

outputFormat

For each query, output a single integer: the maximum mana that Bessie can collect if she must finish at pool \(e\) at time \(s\). If no valid route exists, output 0.

sample

2 1 2
1 100
2 1 10
12 1
10 2

200
1000