D - DDPC特別ビュッフェ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

A 君と B 君はDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のDDPC特別ビュッフェを楽しんでいます。 A 君のトレーには N 個の料理が、 B 君のトレーは M 個の料理が置かれています。 A 君のトレーにある i 番目の料理の美味しさは A_iで、 B 君のトレーにある j 番目の料理の美味しさは B_j で表されます。

とっても仲良しな 2 人はより昼食を楽しむため、A 君のトレーにある料理 1 つと、 B 君のトレーにある料理 1 つを交換するという操作をちょうど K 回行うことにしました。 A 君のトレーにある料理の美味しさの総和が a で、 B 君のトレーにある料理の美味しさの総和が b で表されるとき、 2人の幸福度は a×b で表されます。

K 回交換を行ったあとのありうる幸福度のうち、最大の値を求めなさい。

入力

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

N M K
A_1 A_2 … A_N
B_1 B_2 … B_M
  • 1 行目に A 君と B 君の持っている料理の数を表す整数 N, M (1≦N,M≦55) と料理の交換回数 K(1≦K≦999) が与えられる。
  • 2 行目に A 君のトレーに置かれている i 番目の料理の美味しさを表す整数 A_i (0≦A_i≦22,222) が空白区切りで与えられる。
  • 3 行目に B 君のトレーに置かれている j 番目の料理の美味しさを表す整数 B_j (0≦B_j≦22,222) が空白区切りで与えられる。

出力

ありうる 2 人の幸福度の最大値を 1 行に出力せよ。末尾の改行を忘れないこと。

部分点

この問題には部分点が設定されている。

  • K=1 を満たすデータセットに正解した場合 10 点が与えられる。
  • 0≦A_i,B_j≦55を満たすようなデータセットに正解した場合上記の部分点とは別に 20 点が与えられる。
  • 追加制約のないデータセットに正解した場合さらに 70 点が得られ合計 100 点が得られる。

入力例 1

3 2 1
2 2 3
3 2

出力例 1

36
  • A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。

入力例 2

3 2 2
2 2 2
3 3

出力例 2

36
  • 1 回目の交換で A 君のトレーにある美味しさ 2 の料理と B 君のトレーにある美味しさ 3 の料理を交換し、 2 回目の交換で A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。