32410번 - 용감한 용사 수호

문제

수호는 먹는 걸 좋아하는 모험가다. 하지만 먹고살기 위해서는 돈이 필요하기 때문에 수호는 몬스터를 사냥해서 돈을 벌려고 한다.

수호에게는 공격력과 체력이라는 능력치가 존재하는데, 수호의 초기 공격력과 초기 체력은 각각 정수 $X,Y$이다. 수호는 마을의 상점에서 장비를 구매해서 자신의 공격력과 체력을 올릴 수 있다. 상점은 $N$개의 장비를 판매하고 있는데, 수호가 $i(1\le i\le N)$번째 장비를 착용하면 공격력이 $x_i$만큼 증가하고, 체력이 $y_i$만큼 증가한다. 각 장비는 최대 한 개만 구매할 수 있고, 수호는 $M$개의 장비를 구매해서 착용하려고 한다.

장비를 구매한 수호는 사냥터에서 몬스터들을 사냥한다. 사냥터에는 몬스터가 $K$마리 있는데, $i(1\le i\le K)$번째 몬스터의 공격력과 체력은 각각 정수 $p_i,q_i$이다. 수호가 $i$번째 몬스터를 사냥하기 위해서는 수호의 공격력이 몬스터의 공격력보다 높거나 같고, 체력 또한 몬스터의 체력보다 높거나 같아야 한다. 몬스터를 사냥한 뒤에도 수호의 체력과 공격력은 변하지 않는다. 각 몬스터는 최대 한 번만 사냥할 수 있다.

먹는 걸 좋아하는 수호는 많은 돈을 벌기 위해 최대한 많은 몬스터를 사냥하려고 한다. $M$개의 장비를 적절히 구매해서 착용했을 때, 수호가 사냥할 수 있는 최대 몬스터의 수를 구해보자.

입력

첫째 줄에 정수 $N,M(1\le M\le N\le 300)$과 정수 $X,Y(1\le X,Y\le 300)$가 공백으로 구분되어 주어진다.

둘째 줄부터 $N$개의 줄에 정수 $x_i,y_i(1\le x_i,y_i\le 300)$가 공백으로 구분되어 주어진다. $x_i,y_i$는 $i$번째 장비를 착용했을 때 증가하는 공격력과 체력을 의미한다.

$N+2$번째 줄에 정수 $K(1\le K\le 50,円 000)$가 주어진다.

$N+3$번째 줄부터 $K$개의 줄에 정수 $p_i,q_i(1\le p_i,q_i\le 300)$가 공백으로 구분되어 주어진다. $p_i,q_i$는 $i$번째 몬스터의 공격력과 체력을 의미한다.

출력

$M$개의 장비를 적절히 구매해서 착용했을 때, 수호가 사냥할 수 있는 최대 몬스터의 수를 출력한다.

제한

힌트