题目描述

在召唤师峡谷，不是所有英雄都能单打独斗。有些英雄只有在“羁绊”英雄也被选中时，才能上场。给定召唤空间容量 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开始）

输出格式

输出最大总战斗力。

样例

10 3
2 5
4 11
6 13
1
3 2

24