마나 수집

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)$로 연결되어 있으며, 이는 $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$). 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$)로 이루어진다. 각 질의마다, $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$개의 줄을 출력한다. 각 줄은 질의 하나에 대한 답이다.