페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5476

Mana Collection 5초 512MB

문제

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)로 연결되어 있다. 이 간선은 Bessie가 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로 주어지며, Bessie가 s초 후에 반드시 마나 웅덩이 e에 있어야 할 때, 최대한 모을 수 있는 마나의 양을 구하는 문제이다. (1\le s\le 10^9)


입력

첫 번째 줄에 정수 N과 M이 주어진다.

두 번째 줄에는 각 마나 웅덩이의 초당 마나 생성량 m_1, m_2, \dots, m_N이 주어진다.

다음 M개의 줄에는 세 개의 정수 a_i, b_i, t_i가 주어진다.

• 이는 Bessie가 a_i에서 b_i로 t_i초 동안 이동 가능하다는 뜻이다.

• 같은 방향의 간선 (a_i, b_i)가 여러 번 등장하지 않는다.

그다음 줄에는 정수 Q가 주어진다.

다음 Q개의 줄에는 정수 s와 e가 주어진다.

• 이는 s초 후에 반드시 마나 웅덩이 e에 있어야 할 때, 최대한 모을 수 있는 마나의 양을 구해야 함을 의미한다.


출력

총 Q개의 줄에 대해, 각 쿼리에 대한 답을 한 줄씩 출력한다.


예제1

입력
2 1

1 10

1 2 10

4

5 1

5 2

100 1

100 2
출력
5

50

100

1090

예제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
출력
160000000

239999988050000000

119992550000000


출처

USACO 2023 January Platinum

역링크 공식 문제집만