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)

#5476 upload 4 done 2 how_to_reg 3

Mana Collection timer 5s memory 512MB

#5476

Mana Collection 5s 512MB