J. 召唤师的羁绊选择

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在召唤师峡谷，不是所有英雄都能单打独斗。有些英雄只有在“羁绊”英雄也被选中时，才能上场。给定召唤空间容量 m 和 n 个英雄，每个英雄有体积 w、战斗力 v，部分英雄有“依赖关系”：如果英雄 A 依赖于英雄 B，只有选了英雄 B 才能选英雄 A。请问，如何在不超过空间容量的前提下，选出最大战斗力？

第一行输入整数 m 和 n（1≤m≤200，1≤n≤30）。接下来 n 行，每行输入两个整数，表示第 i 个英雄的体积 w 和战斗力 v。再输入一个整数 k，表示依赖关系对数。接下来 k 行，每行输入两个整数 a b，表示“英雄 a 依赖于英雄 b”（下标从1开始）

输出最大总战斗力。