AT_joigsp2025_i ティーパーティー (Tea Party)

葵はティーパーティーを開催しようと計画している． このティーパーティーには葵を含めた $ 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 $ である． 葵が準備したケーキと紅茶を適切に配るとき，すべての参加者の幸福度の総和として考えられる最大値を求めよ． なお，今回配らなかったケーキについては，葵が別の日に食べるため考えなくてよいものとする． ---

入力は以下の形式で標準入力から与えられる． > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ C_1 $ $ C_2 $ $ \cdots $ $ C_M $ $ D_1 $ $ D_2 $ $ \cdots $ $ D_M $

標準出力に，葵が準備したケーキと紅茶を適切に配るときの，すべての参加者の幸福度の総和として考えられる最大値を $ 1 $ 行で出力せよ．

### 小課題 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 $ 点) 追加の制約はない． --- ### Sample Explanation 1 葵が準備したケーキと紅茶を適切に配るとき，すべての参加者の幸福度の総和の最大値は $ 12 $ である． - 参加者 $ 1 $ にケーキ $ 1 $ と紅茶 $ 1 $ を配る．参加者 $ 1 $ の幸福度は $ 2 + 3 = 5 $ である． - 参加者 $ 2 $ にケーキ $ 3 $ と紅茶 $ 3 $ を配る．参加者 $ 2 $ の幸福度は $ 2 + 1 = 3 $ である． - 参加者 $ 3 $ にケーキ $ 4 $ と紅茶 $ 2 $ を配る．参加者 $ 3 $ の幸福度は $ 4 $ である． どのように配っても，すべての参加者の幸福度の総和が $ 12 $ より大きくならないため， $ 12 $ を出力する． この入力例は小課題 $ 4 $ の制約を満たす． --- ### Sample Explanation 2 この入力例は小課題 $ 3,4 $ の制約を満たす． --- ### Sample Explanation 3 この入力例は小課題 $ 1,4 $ の制約を満たす． --- ### Sample Explanation 4 この入力例は小課題 $ 2,4 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．