Maximizing Candy Count in a Card Chip Game

In this problem, player D is about to play a game against player C. Initially, both players buy v candies as chips. Player C and player D receive cards from a deck. The rules for m rounds are as follows:

• At the beginning of the game, player C receives m cards, each having a suit and a point value. Player D receives n cards.
• In each round, player C plays one card (its suit and point value are revealed) on the table.
• Then, player D may choose to follow by playing a card from his hand of the same suit as the card played by player C. If he cannot (or chooses not to), he forfeits the round.
• If player D forfeits the round, he loses the round.
• If player D plays a card, a comparison of points is done:
  • If the point on D's card is ≥ p_C, then D wins the round.
  • Otherwise, D loses.
• After each round, regardless of the outcome, both players discard the cards they played. Then, the winner takes c candies from the loser. In addition, each player goes to the store and buys candies equal to the point value on the card they played. (For example, if player C played a card with point 3 and player D played one with point 5, then C buys 3 candies, and D buys 5 candies.)
• It is guaranteed that v ≥ c \times m so that no player can be completely wiped out.

Player D has obtained the sequence of cards (including their suits and points) that player C will play in all m rounds. Knowing this information, player D wants to plan his moves (i.e. choose which card to play for each round or to forfeit) so as to maximize his total number of candies at the end of the game.

Your task is to help player D calculate the maximum total number of candies he can have at the end of the game if he plays optimally.

Important: When a round is forfeited by D, no card is played by him and he loses the round automatically. In that case, his extra candy gain from the store is 0 for that round, and he loses c candies due to the round loss. When D plays a card:

• If his card's point value pD ≥ pC (i.e. he wins), his net change for that round is: +c + pD.
• If his card's point value is less than pC (i.e. he loses), his net change is: -c + pD.
• If he forfeits, the net change is: -c.

You can view the effect relative to simply forfeiting a round as follows:

• If D plays a card with point pD and forfeits otherwise, then the additional gain compared to forfeiting is:
  • pD + 2c when pD ≥ pC (win),
  • pD when pD < pC (loss).

Since player D can only use each card in his hand once, and since a card can only be played in a round with a matching suit, you should consider each suit independently. For a given suit, suppose there are a number of rounds where player C plays a card (with points given) and a number of cards in D’s hand (with their corresponding points). You need to choose a pairing between some rounds and some of D's cards such that the total extra gain is maximized.

The final number of candies player D will have is:

[ \text{final candies} = v - m\times c + \sum_{\text{over suits}} (\text{optimal extra gain for that suit}) ]

Given the values of m, n, c, v, and the details of the cards for both players, compute the maximum total number of candies player D can have after m rounds if he plays optimally.

inputFormat

The first line contains four integers: m, n, c, and v where

• m (1 ≤ m ≤ 10⁵) is the number of rounds.
• n (1 ≤ n ≤ 10⁵) is the number of cards in player D's hand.
• c (1 ≤ c ≤ 10⁹) is the candy transfer per round.
• v (v ≥ c × m) is the initial number of candies each player has.

The next m lines each contain a string s and an integer p, representing the suit and point value of the card played by player C in each round.

The following n lines each contain a string s and an integer p, representing the suit and point value of one of player D's cards.

Suits are represented by strings (for example, "H", "D", "S", "C").

outputFormat

Output a single integer: the maximum number of candies player D can have at the end of the game if he plays optimally.

sample

3 3 2 10
H 3
D 5
H 4
H 3
H 5
D 4

24