第24回日本情報オリンピック　一次予選(第1回)

2024年9月16日
情報オリンピック日本委員会

問題文

JOI 君はどら焼きを作ろうとしている．

どら焼きはちょうど 1 つずつの餡と皮から作ることができ，すべての餡と皮には正の整数で表される「美味しさ」が定義されている．1 から N までの番号が付けられた N 種類の餡があり，餡 i (1 ≦ i ≦ N) の美味しさは A_i である．また，1 から M までの番号が付けられた M 種類の皮があり，皮 j (1 ≦ j ≦ M) の美味しさは B_j である．

JOI 君はこれらの餡と皮の組み合わせをすべて試し，N × M 個のどら焼きを作る．各どら焼きの美味しさは，餡と皮の美味しさの和に，餡と皮の美味しさのうち大きい方の値を掛けたものである．

N × M 個のどら焼きの美味しさの総和を求めよ．

制約

• 1 ≦ N ≦ 100．
• 1 ≦ M ≦ 100．
• 1≦ A_i ≦ 100 (1≦ i ≦ N)．
• 1≦ B_j ≦ 100 (1≦ j ≦ M)．
• 入力される値はすべて整数である．

入力

入力は以下の形式で与えられる．
N M
A₁ A₂ … A_N
B₁ B₂ … B_M

出力

N × M 個のどら焼きの美味しさの総和を出力せよ．

答え以外は何も出力しないこと．(入力を促す文章なども出力しないこと．)

解答形式については，練習問題やその解答例 を参考にしても良い．

入力例 1

2 2
1 2
2 5

出力例 1

79

作られる 4 個のどら焼きそれぞれについて，美味しさは以下のようになる．

• 餡 1 と皮 1 が作るどら焼きの美味しさは，餡と皮の美味しさの和である 3 (= 1 + 2) に，餡と皮の美味しさのうち大きい方の値である 2 を掛けた 6 である．
• 餡 1 と皮 2 が作るどら焼きの美味しさは，餡と皮の美味しさの和である 6 (= 1 + 5) に，餡と皮の美味しさのうち大きい方の値である 5 を掛けた 30 である．
• 餡 2 と皮 1 が作るどら焼きの美味しさは，餡と皮の美味しさの和である 4 (= 2 + 2) に，餡と皮の美味しさのうち大きい方の値である 2 を掛けた 8 である．
• 餡 2 と皮 2 が作るどら焼きの美味しさは，餡と皮の美味しさの和である 7 (= 2 + 5) に，餡と皮の美味しさのうち大きい方の値である 5 を掛けた 35 である．

これらの総和より，79 (= 6 + 30 + 8 + 35) を出力すれば良い．

入力例 2

1 5
50
9 7 5 4 1

出力例 2

13800

入力例 3

15 5
5 10 52 31 14 16 19 1 9 20 80 19 11 34 72
20 2 4 9 19

出力例 3

116756