### 问题描述 夏天来临，旅行者受可莉邀请来到了一个名为 "仲夏！幻夜？奇想曲！" 的音乐盛典。旅行者需要收集不同种类的魔法音符来完成曲目。这些魔法音符分布在 $n$ 个岛屿上，每个岛屿都有其特定的音符。岛屿之间存在依赖关系，即访问某些岛屿可能需要先访问其他岛屿并收集到特定音符。 旅行者的背包有容量限制 $W$，需要选择合适的音符组合来完成曲目。给定岛屿的依赖关系和每个岛屿上音符的价值与重量，请帮助旅行者计算如何选择音符以得到最大的价值。 ### 输入格式 第一行输入两个正整数 $n$ 和 $W$，分别表示岛屿的数量和旅行者背包的容量。 接下来 $n$ 行，每行两个非负整数 $v_i$ 和 $w_i$，分别表示第 $i$ 个岛屿的音符价值和体积。 接下来的一行输入一个正整数 $m$，表示接下来会有 $m$ 条依赖关系。 随后的 $m$ 行，每行两个整数 $a, b$，表示获取岛屿 $a$ 的音符之前需要持有岛屿 $b$ 的音符。 ### 输出格式 在一行中输出旅行者可以获得的最大音符价值。 ### 样例输入 ``` 3 15 50 5 80 8 120 12 2 2 1 3 1 ``` ### 样例输出 ``` 130 ``` ### 样例说明 旅行者可以先去岛屿 $1$，然后可以选择去岛屿 $2$ 或岛屿 $3$，但由于背包容量限制，他只能选择岛屿 $2$ 的音符，所以最大价值为 $50+80=130$。 ### 测评数据规模 $1 \le n \le 100$，$1 \le m \le n-1$，$1 \le v_i, w_i \le 10^4$，$1 \le W \le 10^5$。