CF2115E Gellyfish and Mayflower

[Mayflower by Plum](https://www.youtube.com/watch?v=wD6_6R7dhnE/) May, Gellyfish's friend, loves playing a game called "Inscryption" which is played on a directed acyclic graph with $ n $ vertices and $ m $ edges. All edges $ a \rightarrow b $ satisfy $ a

The first line of input contains two integers $ n $ and $ m $ ( $ 1 \leq n \leq 200 $ , $ n - 1 \leq m \leq \min(\frac {n(n-1)} 2, 2000) $ ) — the number of vertices and the number of edges. The $ i $ -th of the following $ n $ lines of input each contains two integers $ c_i $ and $ w_i $ ( $ 1 \leq c_i \leq 200 $ , $ 1 \leq w_i \leq 10^9 $ ) — describing the cards of the Trader on the $ i $ -th vertex. In the following $ m $ lines of input, each line contains two integers $ u $ and $ v $ ( $ 1 \leq u < v \leq n $ ), indicating a directed edge from vertex $ u $ to vertex $ v $ . It is guaranteed that every edge $ (u,v) $ appears at most once. The next line of input contains one single integer $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of queries. In the following $ q $ lines of input, each line contains two integers $ p $ and $ r $ ( $ 1 \leq p \leq n $ , $ 1 \leq r \leq 10^9 $ ). It is guaranteed that for all $ i $ , there exists a path from vertex $ 1 $ to vertex $ i $ .

For each query, output the answer to the query.

For the third query in the first example, we will play the game in the following order: - buy $ 1 $ card with $ 9 $ power from the trader on vertex $ 1 $ , and you'll still have $ 1 $ coin after the trade. - move from vertex $ 1 $ to vertex $ 2 $ . - move from vertex $ 2 $ to vertex $ 3 $ . - buy $ 1 $ card with $ 2 $ power from the trader on vertex $ 3 $ , and you'll have no coins after the trade. In the end, we will have $ 1 $ card with $ 9 $ power and $ 1 $ card with $ 2 $ , so the sum of the power of the cards is $ 9+2=11 $ .For the fifth query in the second example, we will play the game in the following order: - move from vertex $ 1 $ to vertex $ 3 $ . - buy $ 1 $ card with $ 2 $ power from the trader on vertex $ 3 $ , and you'll still have $ 3 $ coins after the trade. - move from vertex $ 3 $ to vertex $ 4 $ . - buy $ 1 $ card with $ 9 $ power from the trader on vertex $ 4 $ , and you'll have no coins after the trade. In the end, we will have $ 1 $ card with $ 2 $ power and $ 1 $ card with $ 9 $ , so the sum of the power of the cards is $ 2+9=11 $ .For the sixth query in the second example, we will play the game in the following order: - move from vertex $ 1 $ to vertex $ 2 $ . - buy $ 1 $ card with $ 5 $ power from the trader on vertex $ 2 $ , and you'll still have $ 3 $ coins after the trade. - move from vertex $ 2 $ to vertex $ 4 $ . - buy $ 1 $ card with $ 9 $ power from the trader on vertex $ 4 $ , and you'll have no coins after the trade. In the end, we will have $ 1 $ card with $ 5 $ power and $ 1 $ card with $ 9 $ , so the sum of the power of the cards is $ 5+9=14 $ .For the seventh query in the second example, we will play the game in the following order: - buy $ 10 $ cards with $ 1000 $ power from the trader on vertex $ 1 $ , and you'll still have $ 1 $ coin after the trade. - move from vertex $ 1 $ to vertex $ 3 $ . - buy $ 1 $ card with $ 2 $ power from the trader on vertex $ 3 $ , and you'll have no coins after the trade. - move from vertex $ 3 $ to vertex $ 4 $ . In the end, we will have $ 10 $ cards with $ 1000 $ power and $ 1 $ card with $ 2 $ power, so the sum of the power of the cards is $ 10 \cdot 1000+2=10\,002 $ .