23754번 - 방문 판매 (Hard)

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

방문 판매를 할 때는 영업 부서에서 정한 매뉴얼에 따라 차례대로 고객을 방문해야 하지만, 매뉴얼을 잃어버린 레오는 전체 방문 순서를 알 수 없어 깊은 고민에 빠졌다. 그러나 기억력이 좋은 레오는 서로 다른 두 고객의 번호의 쌍 $M$개에 대해 어떠한 고객을 먼저 방문해야 하는지 알고 있다. 그래서 레오는 자신의 기억력을 바탕으로 다음과 같은 규칙으로 모든 $N$명의 고객을 방문하기로 결정했다.

1. 아직 방문한 적 없는 고객 중 현재 방문 가능한 모든 고객을 방문 후보로 정한다.
2. 후보로 고른 모든 고객을 고객 번호가 작은 사람부터 오름차순으로 방문한다.
3. 전체 $N$명의 모든 고객을 방문할 때까지 1과 2를 반복한다.

1에서 방문 가능하다는 건 앞서 방문해야 하는 고객이 없거나 그러한 고객을 이미 모두 방문한 경우를 의미한다. 즉, $i$번 고객보다 먼저 방문해야 하는 고객이 존재하지 않거나 그러한 고객을 이미 모두 방문했으면 $i$번 고객은 방문 후보가 된다.

레오가 판매하면서 가지고 다니는 차에는 제품 X, Y가 부족할 일이 없도록 충분히 많은 양을 채운다.

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

첫 번째 줄에 레오가 방문해야 하는 고객 수인 $N$, 기억하는 고객의 방문 순서에 관한 정보의 개수인 $M$, 판매해야 하는 두 제품 X, Y의 할당량인 $X$, $Y$가 정수로 주어진다. ($1 \le N \le 400$, $0 \le M \le N \cdot (N - 1) $, $1 \le X, Y \le 200$)

두 번째 줄부터 $M$개의 줄에 걸쳐 레오가 기억하고 있는 방문 순서에 관한 순서쌍인 $a_i$, $b_i$가 차례로 주어진다. 이는 고객 번호가 $a_i$인 사람을 $b_i$인 사람보다 먼저 방문해야 한다는 의미이다. 같은 순서쌍은 주어지지 않는다. ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le i \le M$)

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

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

어떠한 고객이 제품을 구입한다고 하더라도 할당량을 채울 수 없거나, 고객의 방문 순서가 모순되어 $N$명의 모든 고객을 방문할 수 없어서 방문 판매를 마칠 수 없는 경우에는 $-1$을 출력한다.