Maximizing Deck Strength

On Vito's desk, there are \(N\) red cards numbered from \(1\) to \(N\) and \(M\) blue cards numbered from \(1\) to \(M\). We define a pair as a combination of one red card and one blue card. You are also given \(K\) ordered pairs \((c, p)\). A pair consisting of red card \(c\) and blue card \(p\) is called a good pair if and only if \((c, p)\) is among the given \(K\) pairs.

A deck is any collection of some red cards and some blue cards (possibly empty). The value \(w\) of a deck is defined as the number of good pairs that can be formed using one red card and one blue card from the deck (each good pair is counted once if both cards are chosen).

Let \(r\) and \(b\) be the number of red and blue cards in the deck respectively. The strength of the deck is defined as:

[ \mathrm{strength} = w - X \cdot r - Y \cdot b ]

where \(X\) and \(Y\) are given constants.

Your task is to select a subset of red cards and blue cards to form a deck, so that the strength of the deck is maximized. Note that you are allowed to select no cards at all (i.e. an empty deck, whose strength is \(0\)).

Input constraints: It is guaranteed that \(N\) and \(M\) are small (for example, \(N, M \leq 20\)), so that your algorithm can run in exponential time in \(N\) if needed.

inputFormat

The first line of input contains five integers \(N\), \(M\), \(K\), \(X\) and \(Y\) where:

• \(N\) is the number of red cards.
• \(M\) is the number of blue cards.
• \(K\) is the number of good pairs.
• \(X\) and \(Y\) are the given constants.

The following \(K\) lines each contain two integers \(c\) and \(p\) (with \(1 \le c \le N\) and \(1 \le p \le M\)) indicating that the pair consisting of red card \(c\) and blue card \(p\) is a good pair.

outputFormat

Output a single integer, which is the maximum strength a deck can have.

Note: The empty deck (with strength 0) is a valid option.

sample

3 3 3 3 2
1 1
2 2
3 3

0