题目描述

塔子哥是一位热爱冒险和收藏的小哥哥。最近，他迷上了购买各种精美的周边商品。不过，由于空间有限，塔子哥只能带一个容量为 m 的背包，背包只能装得下体积之和不超过 m 的商品。

商店里有 n 个商品，分别编号为 1 到 n，每个商品都有自己的价值 vali 和体积 wi。塔子哥希望在背包容量的限制下，尽可能地选择价值最高的商品。

然而，塔子哥面临一个难题：有些商品不能同时购买，因为它们会产生不好的化学反应。商店老板给塔子哥设定了 k 组互斥关系，每组关系由两个商品编号 a 和 b 组成，表示编号为 a 的商品和编号为 b 的商品不能同时购买。

塔子哥希望能够找到一种最佳的选择，使得他装入背包中的商品总价值最大。让我们帮塔子哥计算一下，如何在满足背包容量和互斥关系的情况下，获得最大价值的商品组合。

输入格式

第一行输入三个整数 $n$，$m$，$k$，分别表示商品数量、背包容量和互斥关系数量。

接下来 $n$ 行，每行两个整数 $w_i$，$v_i$，分别表示每个物品的体积和价值。

接下来 $k$ 行，每行输入两个整数 $a$，$b$，描述一组互斥关系。

输出格式

一行一个整数表示答案。

3 100 2
15 19
20 30
15 19
1 2
2 3

38

范围

对于 $100\%$ 的数据，满足 $1\le n\le 15$，$1\le m\le 10^9$，$0\le k\le 15$，$1\le w_i,v_i\le 10^9$，$1\le a,b\le n,a\ne b$。