Guaranteed Misère Transformation

In this problem, you are given a modified version of the card game Préférence. The deck consists of \(A\) suits and \(B\) ranks in each suit (ranks from \(1\) to \(B\)). You initially have \(n\) cards. You are allowed to choose any \(x\) cards that are not in your hand and add them. After that, you must drop exactly \(x\) cards from your hand (which now contains \(n+x\) cards) so that your final hand of \(n\) cards becomes a guaranteed misère.

A hand is said to be a guaranteed misère if, for every suit, when you order the cards of that suit in your hand by their ranks as \(b_1 < b_2 < \cdots < b_k\) (where \(k\) is the number of cards of that suit in your hand), the following condition holds: \[ b_i \leq 2i-1 \quad \text{for all } i=1,2,\dots,k. \] If you do not have any cards of a suit (i.e. \(k=0\)), the condition is trivially satisfied.

Your task is to determine the smallest non-negative integer \(x\) (the number of cards to replace) such that you can transform your current hand into a guaranteed misère. You can view this operation as replacing up to \(x\) cards from your initial hand with cards of your choice (from those not originally held) in order to achieve a valid hand. In each suit, you are allowed to drop cards that do not help you meet the condition. For a given suit, if you can keep at most \(f\) cards from your original hand that satisfy the condition (by ensuring the \(i\)-th lowest kept card is \(\leq 2i-1\)), then you must replace the other cards in that suit if you wish to have more cards. Since your final hand must contain exactly \(n\) cards, the minimum number of replacements required is: \[ x = n - \sum_{s=1}^{A} f_s, \] where \(f_s\) is the maximum number of cards you can keep from suit \(s\) while satisfying \(b_i \leq 2i-1\>.

inputFormat

The first line of input contains three integers \(A\), \(B\), and \(n\): the number of suits, the number of ranks in each suit, and the number of cards in your hand, respectively.

The following \(n\) lines each contain two integers \(s\) and \(r\), representing that you hold a card of suit \(s\) (with \(1 \leq s \leq A\)) and rank \(r\) (with \(1 \leq r \leq B\)).

outputFormat

Output a single integer: the smallest possible \(x\) (number of cards to be replaced) such that you can transform your hand into a guaranteed misère.

sample

4 8 5
1 1
1 3
2 2
3 1
4 7

2