C - 最高のトッピングにしような Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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

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

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

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

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

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

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

入力

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

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 点が与えられる。

出力

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

入力例1

3 5
4
3 30
3 40
5 60
7 80

出力例1

100

初期状態ではスペシャルチケットを 3 枚、通常のチケットを 5 枚持っています。例えば以下のような交換を行うと最大値 100 (= 40 + 60) を達成できます。

  • トッピング 2 (チケットが 3 枚必要)をスペシャルチケット 1 枚と通常のチケット 2 枚を用いた交換で入手します。トッピング 2 の嬉しさは 40 です。
  • トッピング 3 (チケットが 5 枚必要)をスペシャルチケット 2 枚と通常のチケット 3 枚を用いた交換で入手します。トッピング 3 の嬉しさは 60 です。

この方法は、スペシャルチケットを 3 (= 1 + 2) 枚、通常のチケットを 5 (= 2 + 3) 枚消費する方法なので実行可能です。

入力例2

3 3
4
3 30
3 40
5 60
7 80

出力例2

70

トッピング 1 とトッピング 2 を入手するのが最適となります。

入力例3

1 5
4
3 30
3 40
5 60
7 80

出力例3

60

トッピング 3 を入手して、チケットを 1 枚余らせるのが最適となります。

入力例4

6 12
4
3 30
3 40
5 60
7 80

出力例4

210

すべてのトッピングを入手できます。