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

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

問題
  どら焼き (Dorayaki) (配点 100点)
  時間制限 : 2 sec / メモリ制限 : 1024 MB

問題文

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

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

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

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

制約

入力

入力は以下の形式で与えられる.
N M
A1 A2 AN
B1 B2 BM

出力

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

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

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


入力例 1

2 2
1 2
2 5

出力例 1

79

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

これらの総和より,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