Description

To make the game a bit more fun, Xiao C and Xiao D each buy $v$ candies as chips.

The rules of onu are as follows:

The game has a total of $m$ rounds and is played by two players, one going first and one going second. Here, we assume the first player is Xiao C, and the second player is Xiao D.

At the very beginning, Xiao C gets $m$ cards, each with a suit and a rank. Xiao D gets $n$ cards.

At the start of each round, Xiao C plays one card and places it on the table to show Xiao D.

After that, Xiao D must follow suit, i.e., play one card from his hand whose suit is the same as the suit of Xiao C’s card. If Xiao D has no valid card, or he chooses to give up (that is, he may choose whether to play a card in the current round), then Xiao C’s card is discarded and the round is skipped; Xiao D is considered to lose the round.

After Xiao D plays a valid card, they compare ranks. If the rank of Xiao D’s card is greater than or equal to the rank of Xiao C’s card, then Xiao D wins; otherwise, Xiao D loses. It is easy to see that there will be no tie.

Finally, the winner takes $c$ candies from the loser. Both players discard the cards they played, and then each buys a number of candies equal to the rank of the card they played. For example, if Xiao C and Xiao D play ranks $3$ and $5$ respectively, then Xiao C buys $3$ candies and Xiao D buys $5$ candies.

To avoid harming their friendship and to prevent one side from winning all of the other’s candies, they have already agreed when buying candies at the beginning that $v \ge c \times m$.

Now, using some mysterious method, Xiao D knows all the cards Xiao C will play in these $m$ rounds. He wants to maximize the number of candies he has after the $m$ rounds are finished. Can you help him find the best strategy?

Input Format

The first line contains four positive integers $n, m, c, v$, with meanings as described above.

In the next $n$ lines, the $i$-th line contains two positive integers $a _i, b _i$, indicating the suit and rank of the $i$-th card that Xiao D initially has.

In the next $m$ lines, the $i$-th line contains two positive integers $a _i, b _i$, indicating the suit and rank of the card that Xiao C will play in round $i$.

Note that there may be cards with both the same suit and the same rank.

Output Format

Output a total of $m + 1$ lines.

The first line outputs a positive integer, representing the maximum number of candies Xiao D can have left under an optimal strategy.

In the next $m$ lines, the $i$-th line outputs one integer, representing the index of the card Xiao D plays in round $i$. If Xiao D skips the round, output -1.

This problem uses Special Judge. If there are multiple optimal strategies, output any one of them.

3 3 1 4
3 5
1 2
2 6
1 6
3 5
1 4

10
2
1
-1

1 2 1 5
1 5
1 8
1 4

10
-1
1

Hint

"Sample 1 Explanation"

Use $(a, b)$ to represent a card with suit $a$ and rank $b$.

Initially, Xiao D has $4$ candies. Xiao C will play three cards in order: $(1, 6), (3, 5), (1, 4)$.

One optimal strategy is:

Round 1: Xiao C plays the first card $(1, 6)$. Xiao D plays the second card $(1, 2)$. Xiao D loses, gets $1$ candy taken away, and buys $2$ candies. Now he has $5$ candies.

Round 2: Xiao C plays $(3, 5)$. Xiao D plays $(3, 5)$. Since the rank is greater than or equal to Xiao C’s card, Xiao D wins, takes $1$ candy, and buys $5$ candies. Now he has $11$ candies.

Round 3: Xiao C plays $(1, 4)$. Since Xiao D already played the second card $(1, 2)$ in round 1, he has no card to play, so he outputs $-1$ and is judged to lose. He gets $1$ candy taken away. Now he has $10$ candies.

"Sample 2 Explanation"

Initially there are $5$ candies.

In round 1, Xiao C plays $(1, 8)$. Xiao D chooses to give up and loses, so he has $5 - 1 = 4$ candies left.

In round 2, Xiao C plays $(1, 4)$. Xiao D plays $(1, 5)$ and wins, gaining $5 + 1$ candies, so in the end Xiao D has $10$ candies.

"Special Judge Notes"

Please read the output format carefully.

Each test point is either $0$ points or full points. If your output has any of the following issues, you will get $0$ points:

• The output format is incorrect, such as missing correct line breaks, outputting strange characters, etc.
• The optimal candy count you output is different from the standard answer.
• The card-playing strategy is invalid, i.e., you play a card that has already been discarded, or you play a card whose suit is different from the suit of the card Xiao C played.
• After playing according to your strategy, Xiao D’s remaining number of candies does not match the number you output on the first line.

Constraints

This problem uses bundled tests.

• Subtask 1 (10 points): $n, m \le 5$.
• Subtask 2 (30 points): $n, m \le 1000$.
• Subtask 3 (20 points): $c = 0$.
• Subtask 4 (20 points): $a _i = 1$.
• Subtask 5 (20 points): no special restrictions.

All testdata guarantees $1 \le n, m, a _i, b _i\le 10 ^5$, $0 \le c \le 10 ^5$, $c \times m \le v \le 10 ^{12}$.

Translated by ChatGPT 5