题目压缩包(内含样例)

压缩包内时限写的是 1 秒，以评测系统给出的 1.6 秒为准。

作为生命的答谢，在与 Irumyuui 搬动她的宝物时，她允许你选取其中总体积不超过 $V$ 的一些物品带走。不过她告诉你，这些宝物之间一共有 $q$ 个限制，其中第 $i$ 个限制 $\left$ 表示 宝物 $x_i$ 和 $y_i$ 不能同时选择，否则会产生毁灭 abyss 的巨大爆炸。现在你想知道，在满足所有给定条件的情况下，能带走的宝物价值之和最大是多少。

第一行三个整数 $n, V, q$ 分别表示宝物的数量，限定的总体积，限制的数量。接下来 $q$ 行每行两个正整数 $x_i,y_i$ 表示 第 $i$ 组限制。接下来 $n$ 行，一行两个整数 $w_i, v_i$ 表示第 $i$ 个宝物的体积和价值。

对于所有数据，满足 $1 \leq n \leq 10^3,0 \leq V \leq 10^4, 1 \leq q \leq 15,1 \leq v_i \leq 10^4, 1 \leq w_i \leq 10^4, 1 \leq x_i, y_i\leq n$

一行一个正整数，表示能带走的宝物价值之和的最大值。