葵はティーパーティーを開催しようと計画している． このティーパーティーには葵を含めた M 人が参加予定であり，参加者には 1 から M までの番号が付けられている． 葵は各参加者に，1 切れのケーキと 1 杯の紅茶を配るつもりである．

ティーパーティーのために，葵は N 切れのケーキ (N \geqq M) と M 杯の紅茶を準備した． ケーキには 1 から N まで，紅茶には 1 から M までの番号が付けられている． ケーキ i (1 \leqq i \leqq N) のブランドは A_i で，おいしさは B_i である． 紅茶 j (1 \leqq j \leqq M) のブランドは C_j で，おいしさは D_j である． 葵は参加者の 幸福度 の総和ができるだけ大きくなるように，参加者にケーキと紅茶を配りたい． 参加者 k (1 \leqq k \leqq M) にケーキ i (1 \leqq i \leqq N) と紅茶 j (1 \leqq j \leqq M) を配ったとき，参加者 k の幸福度は以下のように定まる．

• A_i = C_j のとき，参加者 k の幸福度は B_i + D_j である．
• A_i \neq C_j のとき，参加者 k の幸福度は B_i である．

葵が準備したケーキと紅茶を適切に配るとき，すべての参加者の幸福度の総和として考えられる最大値を求めよ． なお，今回配らなかったケーキについては，葵が別の日に食べるため考えなくてよいものとする．

制約

• 1 \leqq M \leqq N \leqq 200\,000．
• 1 \leqq A_i \leqq N (1 \leqq i \leqq N)．
• 0 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq C_j \leqq N (1 \leqq j \leqq M)．
• 0 \leqq D_j \leqq 10^9 (1 \leqq j \leqq M)．
• 入力される値はすべて整数である．

小課題

1. (8 点) D_j = 0 (1 \leqq j \leqq M)．
2. (19 点) B_i = 0 (1 \leqq i \leqq N)．
3. (31 点) A_i = i (1 \leqq i \leqq N)，C_j = j (1 \leqq j \leqq M)．
4. (42 点) 追加の制約はない．

入力例 1

4 3
1 1 2 3
2 1 2 4
1 1 2
3 1 1

出力例 1

12

葵が準備したケーキと紅茶を適切に配るとき，すべての参加者の幸福度の総和の最大値は 12 である．

• 参加者 1 にケーキ 1 と紅茶 1 を配る．参加者 1 の幸福度は 2 + 3 = 5 である．
• 参加者 2 にケーキ 3 と紅茶 3 を配る．参加者 2 の幸福度は 2 + 1 = 3 である．
• 参加者 3 にケーキ 4 と紅茶 2 を配る．参加者 3 の幸福度は 4 である．

どのように配っても，すべての参加者の幸福度の総和が 12 より大きくならないため，12 を出力する．

この入力例は小課題 4 の制約を満たす．

入力例 2

5 3
1 2 3 4 5
4695 53325 57544 74342 81986
1 2 3
59037 23296 16434

出力例 2

232949

この入力例は小課題 3,4 の制約を満たす．

入力例 3

4 3
2 1 3 1
52 49 72 31
3 1 3
0 0 0

出力例 3

173

この入力例は小課題 1,4 の制約を満たす．

入力例 4

5 2
1 1 2 3 5
0 0 0 0 0
1 1
3 1

出力例 4

4

この入力例は小課題 2,4 の制約を満たす．