Door-to-Door Sales (Hard)

SG Group has just released two revolutionary products, X and Y. Leo, the top salesman working as a traveling salesperson in SG Group's sales department, must visit the homes of all $N$ customers and sell these two products in the given quotas $X$ and $Y$. Each customer is numbered from $1$ to $N$, and if a visit to customer $i$'s home results in a successful sale, the amounts of products X and Y that can be sold are given as $x_i$ and $y_i$, respectively. However, some customers may refuse to buy the products even when visited, resulting in a failed sale.

When making door-to-door sales, the customers must be visited in order according to the manual set by the sales department, but Leo, having lost the manual, fell into deep thought because he cannot know the full visit order. However, Leo has a good memory and knows, for $M$ pairs of distinct customer numbers, which customer must be visited first. So Leo decides to visit all $N$ customers based on his memory using the following rules.

1. Among the customers not yet visited, all customers who are currently visitable are chosen as visit candidates.
2. All customers chosen as candidates are visited in ascending order of customer number, starting from the smallest.
3. Steps 1 and 2 are repeated until all $N$ customers have been visited.

In step 1, "visitable" means that there is no customer who must be visited before them, or that all such customers have already been visited. In other words, if there is no customer who must be visited before customer $i$, or if all such customers have already been visited, then customer $i$ becomes a visit candidate.

The car Leo carries while selling is filled with enough quantities of products X and Y so that they never run short.

Leo wonders how few customers he must sell both products X and Y to in this door-to-door sales trip to meet the given quotas. Find the minimum number of customers who must be made to buy the products in order to visit all $N$ customers in a way that satisfies the visit order and meet the quotas, and the number of the customer who succeeds in the sale last.

The first line gives the number of customers Leo must visit, $N$, the number of pieces of information about the customer visit order he remembers, $M$, and the quotas of the two products X and Y to be sold, $X$ and $Y$, as integers. ($1 \le N \le 400$, $0 \le M \le N \cdot (N - 1)$, $1 \le X, Y \le 200$)

From the second line, across $M$ lines, the ordered pairs $a_i$, $b_i$ concerning the visit order Leo remembers are given in order. This means that the customer numbered $a_i$ must be visited before the customer numbered $b_i$. The same ordered pair is not given more than once. ($1 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le i \le M$)

From line $M + 2$, across $N$ lines, for customers $1$ through $N$, the amounts $x_j$ and $y_j$ of the two products X and Y that the customer buys when a visit results in a successful sale are given as integers. ($1 \le x_j, y_j \le 200$, $1 \le j \le N$)

Print the minimum number of customers who must have a successful sale in order to visit all $N$ customers in a way that satisfies the visit order and meet the quotas. Then, on the next line, print the number of the customer who succeeds in the sale last; if there are multiple possible numbers, print the number of the customer whose position in the visit order is earliest among them.

If the quotas cannot be met even if any customer buys the products, or if the visit order is contradictory and all $N$ customers cannot be visited so the door-to-door sales cannot be completed, print $-1$.