Problem Statement

私の行きつけの飲食店では、食事をすることでチケットを得ることができる。

チケットは、トッピングとの交換に必須なスペシャルチケットと、通常のチケットの $2$ 種類存在する。

このお店には $N$ 種類のトッピングがあり、トッピング $i$ は、$t_i$ 枚のチケットと交換することによって入手できる。このお店ではチケットを組み合わせて複数種類のトッピングを入手することもできるが、同じトッピングを複数回入手することはできない。

交換の際、スペシャルチケットも通常のチケットも区別なく $1$ 枚として数えられるが、交換で用いるチケットには、各トッピングごとにスペシャルチケットが $1$ 枚以上含まれなければならない。例えば $4$ 枚のチケットと交換できるトッピングがあった場合、以下の $4$ 通りの交換方法が考えられる。

• スペシャルチケット $1$ 枚と通常のチケット $3$ 枚の組み合わせ。
• スペシャルチケット $2$ 枚と通常のチケット $2$ 枚の組み合わせ。
• スペシャルチケット $3$ 枚と通常のチケット $1$ 枚の組み合わせ。
• スペシャルチケット $4$ 枚のみからなる組み合わせ。

またトッピングにはそれぞれ嬉しさという正の整数が決められていて、トッピング $i$ を入手した時の嬉しさは $h_i$ である。

今日は特別な日なので、現在持っているチケットをうまく使用して、入手したトッピングの嬉しさの合計値を最大化させたい。チケットとトッピングの情報から、嬉しさの合計値として考えられる最大値を求めるプログラムを作成せよ。

Input

入力は以下の形式で標準入力から与えられる。

X Y
N
t_1 h_1
t_2 h_2
:
t_N h_N

• $1$ 行目には、持っているチケットの枚数を表す $2$ つの整数 $X (1 ≦ X ≦ 300)$ と $Y (0 ≦ Y ≦ 300)$ が空白区切りで書かれている。これは、最初にスペシャルチケットを $X$ 枚、通常のチケットを $Y$ 枚持っていることを表す。
• $2$ 行目には、トッピングの種類数を表す整数 $N (1 ≦ N ≦ 300)$ が与えられる。
• $3$ 行目から $N$ 行には、トッピングに関する情報を表す $2$ つの整数 $t_i (1 ≦ t_i ≦ 600)$, $h_i (1 ≦ h_i ≦ 5,000,000)$ が空白区切りで与えられる。これは、トッピング $i$ がチケット $t_i$ 枚と交換することで入手でき、入手したことで得られる嬉しさが $h_i$ であることを表す。

部分点

この問題には部分点が設定されている。

• $X ≦ 50$, $Y ≦ 50$, $N ≦ 50$, $t_i ≦ 100 (1 ≦ i ≦ N)$ を満たすデータセット $1$ に正解した場合は、$30$ 点が与えられる。
• 追加制約のないデータセット $2$ に正解した場合は、上記とは別に $70$ 点が与えられる。

Output

嬉しさの合計値として考えられる最大値を $1$ 行に出力せよ。出力の末尾にも改行を入れること。