B - Doctor Course Is Recommended / D進どうですか？

Story

DのひとはD進を決意したので、博士後期課程入学試験を受けることにした。筆記試験はマークシート形式であった。自身の専門分野の問題ばかりだったので、Dのひとはすぐにすべての正答を導くことができた。しかし、ここで大きな問題に気づいた。Dのひとは宗教上の理由から、解答用紙には'D'としか書くことができなかったのだ。また、'D'と書くためには尋常ではない集中力を使うため，'D'と書くことのできる個数も決まっている。Dのひとが本当にD進することができるか調べるため、解答・配点を踏まえ、上記の条件を満たした上で得られる最大の得点を求めてみよう。

Problem

'A','B','C','D','E'の5択からなるマークシート問題がある。1つの解答欄は空欄1マス、もしくは2マスから構成されており、それぞれの解答欄について、マス全てが想定されている解答と等しいとき、解答欄に割り当てられた点数を得る。解答欄毎の解答と配点が与えられる。D個のマスまで'D'とマークし、残りのマスを空マスにしなければならないとき、得られる点数の最大値を求めよ。

Input

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

D
x
a_1 p_1
...
a_x p_x
y
b_1c_1 q_1
...
b_yc_y q_y

1行目は、'D'と書くことのできる最大回数を表す1つの整数Dからなる。 2行目は、空欄1マスからなる解答欄の個数を表す1つの整数xからなる。続くx行は、空欄1マスからなる解答欄の情報が与えられる。 i+2行目(1 \leq i \leq x)は空欄1マスからなるi番目の解答欄の正答を表す文字a_i、配点を表す整数p_iが空白区切りで書かれている。 x+3行目は、空欄2マスからなる解答欄の個数を表す1つの整数yからなる。続くy行は、空欄2マスからなる解答欄の情報が与えられる。 j+x+3行目(1 \leq j \leq y)は空欄2マスからなるj番目の解答欄の正答を表す2つの文字b_jとc_j、配点を表す整数q_jからなる。 b_jとc_jの間に空白は存在しないが、c_jとq_jの間は空白で区切られている。

制約:

1 \leq D \leq 13 (=0xD)
0 \leq x, 0 \leq y, 1 \leq x + 2y \leq 20
a_i, b_j, c_j \in \{A,B,C,D,E\}

Output

上記の制約を満たして得られる最大得点を1行に出力せよ。行の最後では必ず改行を行うこと。

Sample Input 1

Sample Output 1

1,2番目の解答欄にDと記入し、3番目の解答欄を空白とすることで最大得点80が得られる。

Sample Input 2

4
0
2
DB 60
DD 40

Sample Output 2

2つのマスからなる解答欄は両方とも正解しなければ得点が得られない。

Sample Input 3

13
2
C 15
A 23
2
BD 42
EE 20

Sample Output 3

D進だめです。

Sample Input 4

Sample Output 4

Sample Input 5

Sample Output 5

Source: https://onlinejudge.u-aizu.ac.jp/problems/2576