E. Гелифиш и эпигея
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод
Mayflower by Plum

Мэй, подруга Гелифиша, любит играть в игру под названием «Inscryption», которая играется на направленном ациклическом графе с $$$n$$$ вершинами и $$$m$$$ рёбрами. Все рёбра $$$ a \rightarrow b$$$ удовлетворяют условию $$$a \lt b$$$.

Вы начинаете на вершине $$$1$$$ с некоторым количеством монет. Вам нужно перемещаться от вершины $$$1$$$ к вершине, где находится босс, по направленным рёбрам, а затем сразиться с финальным боссом.

Каждая из $$$n$$$ вершин графа содержит Торговца, который продаст вам карту с силой $$$w_i$$$ за $$$c_i$$$ монет. Вы можете покупать столько карт, сколько хотите, у каждого Торговца. Однако вы можете торговать с торговцем на $$$i$$$-й вершине только если вы находитесь на $$$i$$$-й вершине.

Чтобы победить босса, вы хотите, чтобы сумма сил ваших карт была как можно больше.

Вам предстоит ответить на следующие $$$q$$$ запросов:

  • Даны целые числа $$$p$$$ и $$$r$$$. Если финальный босс находится на вершине $$$p$$$, и у вас изначально $$$r$$$ монет, какова максимально возможная сумма сил ваших карт для сражения с финальным боссом? Обратите внимание, что вы можете торговать картами на вершине $$$p$$$.
Входные данные

Первая строка ввода содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 200$$$, $$$n - 1 \leq m \leq \min(\frac {n(n-1)} 2, 2000)$$$) — количество вершин и количество рёбер.

$$$i$$$-я из следующих $$$n$$$ строк ввода содержит по два целых числа $$$c_i$$$ и $$$w_i$$$ ($$$1 \leq c_i \leq 200$$$, $$$1 \leq w_i \leq 10^9$$$) — описание карты Торговца на $$$i$$$-й вершине.

В следующих $$$m$$$ строках ввода содержится по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u \lt v \leq n$$$) — направленное ребро от вершины $$$u$$$ к вершине $$$v$$$. Гарантируется, что каждое ребро $$$(u,v)$$$ появляется не более одного раза.

Следующая строка ввода содержит одно целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество запросов.

В следующих $$$q$$$ строках ввода содержится по два целых числа $$$p$$$ и $$$r$$$ ($$$1 \leq p \leq n$$$, $$$1 \leq r \leq 10^9$$$).

Гарантируется, что для всех $$$i$$$ существует путь от вершины $$$1$$$ до вершины $$$i$$$.

Выходные данные

Для каждого запроса выведите ответ на запрос — максимально возможную сумму сил карт.

Примеры
Входные данные
3 2
3 9
2 5
1 2
1 2
2 3
6
1 4
2 4
3 4
1 5
2 5
3 5
Выходные данные
9
10
11
9
14
14
Входные данные
4 4
10 1000
2 5
1 2
3 9
1 2
1 3
2 4
3 4
9
2 3
3 3
4 1
4 2
4 4
4 5
4 101
4 102
4 103
Выходные данные
5
6
2
5
11
14
10002
10005
10009
Входные данные
6 8
9 5
4 1
8 9
10 4
9 4
8 2
3 5
4 6
3 4
2 3
1 2
2 5
4 5
1 3
10
3 12
1 9
6 47
2 19
1 129
5 140
2 148
1 63
2 43
3 102
Выходные данные
10
5
46
10
70
154
81
35
21
109
Примечание

Для третьего запроса в первом примере мы будем играть в игру в следующем порядке:

  • купим $$$1$$$ карту с $$$9$$$ силой у торговца на вершине $$$1$$$, и у нас останется $$$1$$$ монета после торговли.
  • переместимся с вершины $$$1$$$ на вершину $$$2$$$.
  • переместимся с вершины $$$2$$$ на вершину $$$3$$$.
  • купим $$$1$$$ карту с $$$2$$$ силой у торговца на вершине $$$3$$$, и у нас не останется монет после торговли.
В конце у нас будет $$$1$$$ карта с $$$9$$$ силой и $$$1$$$ карта с $$$2$$$, так что сумма сил карт составит $$$9+2=11$$$.

Для пятого запроса во втором примере мы будем играть в игру в следующем порядке:

  • переместимся с вершины $$$1$$$ на вершину $$$3$$$.
  • купим $$$1$$$ карту с $$$2$$$ силой у торговца на вершине $$$3$$$, и у нас останется $$$3$$$ монеты после торговли.
  • переместимся с вершины $$$3$$$ на вершину $$$4$$$.
  • купим $$$1$$$ карту с $$$9$$$ силой у торговца на вершине $$$4$$$, и у нас не останется монет после торговли.
В конце у нас будет $$$1$$$ карта с $$$2$$$ силой и $$$1$$$ карта с $$$9$$$, так что сумма сил карт составит $$$2+9=11$$$.

Для шестого запроса во втором примере мы будем играть в игру в следующем порядке:

  • переместимся с вершины $$$1$$$ на вершину $$$2$$$.
  • купим $$$1$$$ карту с $$$5$$$ силой у торговца на вершине $$$2$$$, и у нас останется $$$3$$$ монеты после торговли.
  • переместимся с вершины $$$2$$$ на вершину $$$4$$$.
  • купим $$$1$$$ карту с $$$9$$$ силой у торговца на вершине $$$4$$$, и у нас не останется монет после торговли.
В конце у нас будет $$$1$$$ карта с $$$5$$$ силой и $$$1$$$ карта с $$$9$$$, так что сумма сил карт составит $$$5+9=14$$$.

Для седьмого запроса во втором примере мы будем играть в игру в следующем порядке:

  • купим $$$10$$$ карт с $$$1000$$$ силой у торговца на вершине $$$1$$$, и у нас останется $$$1$$$ монета после торговли.
  • переместимся с вершины $$$1$$$ на вершину $$$3$$$.
  • купим $$$1$$$ карту с $$$2$$$ силой у торговца на вершине $$$3$$$, и у нас не останется монет после торговли.
  • переместимся с вершины $$$3$$$ на вершину $$$4$$$.
В конце у нас будет $$$10$$$ карт с $$$1000$$$ силой и $$$1$$$ карта с $$$2$$$ силой, так что сумма сил карт составит $$$10 \cdot 1000+2=10\,002$$$.