Bessie se ha interesado recientemente por la magia y necesita recolectar maná para un conjuto muy importante. Bessie tiene ~N~ estanques de maná, el i-ésimo del cual acumula ~m_i~ maná por segundo. Los estanques están conectados por una colección de ~M~ arcos dirigidos ~(a_i,b_i,t_i)~, denotando que ella puede viajar de ~a_i~ a ~b_i~ en ~t_i~ segundos. Cuando Bessie está presente en un estanque, ella puede recolectar todo el maná almacenado en esa ubicación, vaciándola. En el tiempo 0, todos los estanques de maná están vacíos, y Bessie puede elegir cualquier estanque para comenzar.

Responda ~Q~ preguntas, cada una especificada por dos enteros ~s~ y ~e~. Para cada pregnta, determine la cantidad máxima de maná que Bessie puede recolectar en ~s~ segundos si ella debe estar en el estanque ~e~ al final del segundo s-ésimo.

Entrada

• La primera línea contiene ~N~ y ~M~.
• La sigiente línea contiene ~m_1,m_2,...,m_N~.
• Las ~M~ líneas siguientes contienen ~a_i,b_i,t_i~. Ningún par ordenado ~(a_i,b_i)~ aparece más de una vez en la entrada.
• La siguiente línea contiene ~Q~.
• Las ~Q~ líneas siguienes contienen dos enteros ~s~ y ~e~.

Salida

~Q~ líneas, una para cada pregunta.

Restricciones

• ~1 \leq N \leq 18~
• ~1 \leq m_i \leq 10^8~
• ~0 \leq M \leq N(N-1)~
• ~1 \leq a_i,b_i \leq N, a_i \neq b_i~
• ~1 \leq t_i \leq 10^9~
• ~1 \leq Q \leq 2 \cdot 10^5~
• ~1 \leq s \leq 10^9~
• ~1 \leq e \leq N~

Ejemplo #1 de Entrada

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

Ejemplo #1 de Salida

5
50
100
1090

Primera pregunta: Bessie toma 5 maná del estanque 1 después de 5 segundos.

Segunda pregunta: Bessie toma 50 maná del estanque 2 después de 5 segundos.

Tercera pregunta: Bessie toma 100 maná del estanque 1 después de 100 segundos.

Cuarta pregunta: Bessie toma 90 maná del estanque 1 después de 90 segundos y 1000 maná del estanque 2 después de 100 segundos.

Ejemplo #2 de Entrada

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

Ejemplo #2 de Salida

160000000
239999988050000000
119992550000000

Un ejemplo donde Bessie puede recolectar cantidades de maná mucho más grandes.

Calificación

Entradas	Restricciones adicionales
3-4	~N \le 10~, ~Q \leq 100~
5-9	~N \leq 10~
10-14	~Q \leq 100~
15-17	~N = 16~
18-20	~N = 17~
21-24	Sin restricciones adicionales

USACO 2023 January Contest, Platinum Problem 2. Mana Collection.