题目描述

实验室有 $n$ 台设备，第 $i$ 台设备的功率为 $w_i$，运行它能产生 $v_i$ 的价值。实验室总供电为 $W$。

此外有 $m$ 对设备 $(x, y)$ 存在冲突，不能同时开启。

求在「总功率不超过 $W$」且「不违反任何冲突」的前提下，能获得的最大总价值。允许一台都不开。

输入格式

第一行两个整数 $n, W$（$1 \le n \le 16$，$1 \le W \le 10^5$）。

接下来 $n$ 行，每行两个整数 $w_i, v_i$（$1 \le w_i \le W$，$1 \le v_i \le 10^4$）。

接下来一行一个整数 $m$（$0 \le m \le n(n-1)/2$）。

接下来 $m$ 行，每行两个整数 $x, y$（$1 \le x < y \le n$），表示 $x$ 与 $y$ 不能同时开启。

输出格式

一个整数，表示最大总价值。

样例 #1

3 10
4 5
6 7
5 6
1
1 3

12

开 1、2 号设备，功率 $4+6=10$，价值 $5+7=12$。开 1、3 号违反冲突；开 2、3 号功率 11 超限。

提示

对于 30% 的数据，$n \le 10$；对于 100% 的数据，$n \le 16$，$W \le 10^5$。