\(1 \le K \le N \times M\) という制約でも対応できる解法を紹介します。

まず、上位 \(K\) 番目の値が何かを求めましょう。これは、 決め打ち二分探索 という手法で実現可能です。

• 答えを \(x\) だと仮定する。
• もし \(x\) 以上の値が \(K\) 個以上あれば答えは \(x\) 以上であり、そうでないなら答えは \(x\) 未満である。
• この \(x\) を二分探索する。

欲しいものは以下です。

• \(f(x) = \{\) \(x\) 以上の値がいくつ存在するか \(\}\)

この \(f\) は以下のように作ることができます。

• \(A,B\) を予め昇順ソートしていく。
• \(A\) の各要素 \(A_i\) について、 \(A_i \times B_j \ge x\) なる \(j\) がいくつ存在するかを求めたい。
• これには、 C 問題でも説明した尺取り法が利用できる。具体的には、以下のようにすればよい。
  • \(j=M+1\) と初期化する。
  • \(i=1,2,\dots,N\) について、以下を繰り返す。
    • \(A_i \times B_{j-1} \ge K\) である限り、 \(j\) を減算し続ける。
    • \(A_i\) の相手として実現可能なのが \(B_j,B_{j+1},\dots,B_M\) であることが分かる。
  • \(i\) が増えるにつれて、相手として実現可能な \(B_j\) として最小の \(j\) が (広義) 単調減少となることに注意されたい。

これで、 \(f\) を作ることができました。
では、 \(K\) 番目までの値の総和はどのように求めればよいでしょうか？
次は、以下を用意します。

• \(g(x) = \{\) \(x\) 以上の値の総和はいくらか \(\}\)

こうすることで、 \(K\) 番目の値が \(x\) であるとき、答えは \(g(x+1) + x \times (K-f(x+1))\) であることが分かります。
この \(g\) は \(f\) を少し改造すれば実現可能です。以降は読者への宿題とします (実装例に内容を示します)。
ヒント: 累積和の考えを利用します。

全体で時間計算量 \(O(N \log A_i)\) でこの問題に正解できます。一部の時間計算量 \(O(N \log A_i \log N)\) かかる解法でもこの問題に正答できるかもしれません。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

using ll=long long;

ll f(ll x,vector<ll> &A,vector<ll> &B){
  ll N=A.size();
  ll M=B.size();
  ll cnt=0;
  ll rp=M;
  for(ll i=0;i<N;i++){
    while(rp>0 && A[i]*B[rp-1]>=x){rp--;}
    cnt+=(M-rp);
  }
  return cnt;
}

ll g(ll x,vector<ll> &A,vector<ll> &B){
  ll N=A.size();
  ll M=B.size();
  ll res=0,sum=0;
  ll rp=M;
  for(ll i=0;i<N;i++){
    while(rp>0 && A[i]*B[rp-1]>=x){
      rp--;
      sum+=B[rp];
    }
    res+=sum*A[i];
  }
  return res;
}

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> A(N),B(M);
  for(auto &nx : A){cin >> nx;}
  for(auto &nx : B){cin >> nx;}
  sort(A.begin(),A.end());
  sort(B.begin(),B.end());

  ll lef=0,rig=2e10;
  while(lef<=rig){
    ll te=(lef+rig)/2;
    if(f(te,A,B)<K){rig=te-1;}
    else{lef=te+1;}
  }

  ll res=g(rig+1,A,B);
  res+=rig*(K-f(rig+1,A,B));

  cout << res << "\n";
  return 0;
}