No.11 カードマッチ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 209
作問者 : yuki2006yuki2006

2 ProblemId : 30 / 出題時の順位表

問題文

Jenは\(W \times H\)枚のカードでトランプゲームをしている。
Jenは(表面を見ることができる)手札にあるいずれかのカードと、手札以外にあるカードのマッチするカードの枚数を知りたくなった。

このトランプは、マークが\(W\)種類あり、数字は\(1\)から\(H\)で構成されており、組み合わせの重複はないとする。
ここでマッチするとは、マークまたは数字のどちらかが一致するカードのことである。

今、手札には\(N\)枚のカードがあり、「手札のカード以外」のマッチするカードの枚数を求めてください。

\(W \times H\) が \(2^{32}\) 以上となる場合があります。

入力

\(W\)
\(H\)
\(N\)
\(S_1\ K_1\)
\(S_2\ K_2\)
\(\dots\)
\(S_i\ K_i\)
\(\dots\)
\(S_N\ K_N\)

\(1\)行目に、トランプのマークの種類を表す整数\(W\ (1 \leq W \leq 1,000,000) \) が与えられます。
\(2\)行目に、トランプの数値の最大値を表す整数\(H\ (1 \leq H \leq 1,000,000) \)が与えられます。
\(3\)行目に、手元にあるカードの枚数を表す整数\(N\ (1 \leq N \leq min(W \times H, 100)) \)が与えられます。
続く\(N\)行に、手元にあるカードのマークと数値を表す\(S_i\ (1 \leq S_i \leq W) \) および \(K_i\ (1 \leq K_i \leq H) \) が空白区切りで与えられます。
$i \neq j$のときは、$(S_i, K_i)$と$(S_j, K_j)$の値の組は、異なることが保証される。

出力

「手札のカード以外」のマッチするカードの枚数を求めてください。

サンプル

サンプル1
入力
2
5
1
1 1
出力
5

\(2\)種類のマークと\(5\)つの数字の組み合わせのトランプを使用する。
この場合
「マーク\(1\)の\(1\)以外の\(4\)種類」と、「マーク\(2\)の\(1\)」がマッチする。

サンプル2
入力
4
13
3
1 1
2 1
2 5
出力
27

現実のトランプのセットと同様である。
この時マッチするのは
「マーク\(1\)の\(1\)以外」と「マーク\(2\)の\(1,5\)以外」と「マーク\(3\)とマーク\(4\)の\(1\)と\(5\)」である。

サンプル3
入力
4
13
4
1 5
2 6
3 7
4 8
出力
48

サンプル4
入力
3
2
2
1 1
2 1
出力
3

提出ページヘ