题目描述

一轮有三个大小为n的正整数集合 $X,Y,Z$ ，其中 $X=Y=Z=$ {1,2,···,n}。

一轮想要构造若干个三元组 $(x,y,z)$ ，其中 $x∈X,y∈Y,z∈Z$ 并且集合里面每个数只能用一次，且每个三元组必须满足： $(x,y)$ 不属于一个一轮给定的讨厌集合 $A$ ，且 $(x,z)$ 属于一个一轮给定的喜好集合 $B$ 。

一轮发现，在严格遵守上述条件的情况下，能构造的三元组太少了，为了提升构造数量，他决定允许自己额外构造k个原本不被允许的三元组（即该三元组可以无视集合A和集合B的约束）。

请问一轮最多能构造多少个三元组？

输入格式

第一行四个整数 $n,k,p,q$ ，分别表示集合大小、允许的非法三元组数量、讨厌集合A的大小、喜好集合B的大小。

接下来 $p$ 行，每行两个整数 $x,y$ ，表示 $(x,y)∈A$ 。

接下来 $q$ 行，每行两个整数 $x,z$ ，表示 $(x,z)∈B$ 。

输出一个整数，表示一轮能构造的三元组最大数量。

A= {(1,1),(2,2)}

B= {(1,2),(2,1)}

检查所有可能：

· (1,2,2):(1,2)∉A,(1,2)∈B→合法

· (2,1,1):(2,1)∉A,(2,1)∈B→合法

其他组合均不合法。

此时集合内无法选出数字了，所以答案为2

$1 \le k \le n \le 200,0 \le p,q \le n^2$