**Замечание: Время на тест для этой задачи 5s, в 2.5 больше чем по умолчанию.
Ограничение по памяти в этой задаче 512MB, в два раза больше чем по умолчанию.**
У Беси есть \(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\)).
Когда Беси находится в бассейне, она может собрать все маны, сохранённые
в этом бассейне, опустошая его. В момент времени \(0\) все бассейны с маной пусты.
Беси может выбрать с какого бассейна стартовать.
Ответьте на \(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\)-ой секунды.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\) и
\(M\).
Следующая строка содержит \(m_1,m_2,\dots, m_N\).
Следующие \(M\) строк содержат \(a_i,b_i,t_i\). Никакая упорядоченная пара
(ai,bi)$ не появится на вводе более одного раза.
Следующая строка содержит \(Q\).
Следующие \(Q\) содержат по два целых числа \(s\) и \(e\).
ФОРМАТ ВЫВОДА (на экран / stdout):
\(Q\) строк, по одной для каждого запроса
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2
|
5
50
100
1090
|