23748번 - 방문 판매

문제

SG그룹은 이번에 획기적인 제품 X, Y를 출시했다. SG그룹의 영업 부서에서 외판원으로 일하는 판매왕 레오는 이 두 제품을 주어진 각 할당량 $X,ドル $Y$만큼 $N$명의 고객의 집을 모두 방문하여 팔아야 한다. 고객마다 1ドル$번부터 $N$번까지 번호가 주어지고, $i$번 고객의 집에 방문하여 판매에 성공했을 때 팔 수 있는 제품 X, Y의 양이 각각 $x_i,ドル $y_i$로 주어진다. 그러나 어떤 고객은 방문하더라도 제품 구매를 거절하여 판매에 실패할 수 있다.

방문 판매를 할 때는 영업 부서에서 정한 매뉴얼에 따라 1ドル$번 고객부터 $N$번 고객까지 오름차순으로 한 번씩 방문해야 한다. 또한, 레오가 판매하면서 가지고 다니는 차에는 제품 X, Y가 부족할 일이 없도록 충분히 많은 양을 채운다.

레오는 이번 방문 판매로 최소 몇 명의 고객에게 두 제품 X, Y를 팔아야 주어진 할당량을 채울 수 있는지 궁금해졌다. 방문 순서를 만족하면서 할당량을 채우기 위해 제품을 구매하도록 만들어야 하는 최소 고객의 수와 이때 가장 마지막으로 판매에 성공하는 고객 번호를 구해보자.

입력

첫 번째 줄에 레오가 방문해야 하는 고객 수인 $N$과 판매해야 하는 두 제품 X, Y의 할당량인 $X,ドル $Y$가 정수로 주어진다. (1ドル \le N \le 50,ドル 1ドル \le X, Y \le 100$)

두 번째 줄부터 $N$개의 줄에 걸쳐 1ドル$번부터 $N$번 고객까지 각 고객을 방문하여 판매에 성공했을 때 해당 고객이 구입하는 두 제품 X, Y의 양인 $x_i$와 $y_i$가 정수로 주어진다. (1ドル \le x_i, y_i \le 100,ドル 1ドル \le i \le N$)

출력

방문 순서를 만족하면서 할당량을 채우기 위해 제품 판매에 성공해야 하는 최소 고객의 수를 출력한다. 이때 마지막으로 판매에 성공하는 고객의 번호를 그 다음 줄에 출력하는데, 가능한 번호가 여러 개이면 그중 가장 작은 값을 출력한다.

어떠한 고객이 제품을 구입한다고 하더라도 할당량을 채울 수 없는 경우에는 $-1$을 출력한다.

제한

힌트