Description

给你两个数列A=(a1,a2,a3,…,an)和B=(b1,b2,b3,…,bm)，把ai (1<=i<=n)和bj (1<=j<=m)乘起来，得到一个新的有m*n个数的数列。把这个序列排列成非递减数列，然后请找出排在第k位的数。

Input

输入有多组数据。
每组数据的第一行包含三个整数：n(1<=n<=10000), m(1<=m<=10000), k(1<=k<=m*n).
第二行包含n个整数，表示数列A。
第三行包含m个整数，表示数列B。
所有数列A和B里的数字范围是 [0, 10000].
每组数据之后有一个空行。

Output

每组数据输出一行，为答案。

Sample Input

1 3 3
1
3 2 1

3 3 7
1 2 3
1 2 3

Sample Output

3
6

Data Constraint

对于所有数据，1<=n<=10000，1<=m<=10000，1<=k<=m*n，0<=ai<=10000, 0<=bj<=10000。

赛时

暴力

正解

二分套二分，先二分个mid为答案，然后check一下，看其是的位置是不是>=k，若是，r=mid-1,ans=mid,否则，l=mid+1;

之后check先枚举个i从1到n，用a[i]去乘b的每一个数，若小于x（check（int x）），则x的位置就+1。

但显然也会爆，所以b数组也来个二分，就Ok了

代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;int n,m,k,l,r,mid,ans,a[10007],b[10007];inline int read(){int a=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){a=a*10+ch-'0';ch=getchar();}return a;
}int check(int x){int l,r,mid,t,cnt=0;for(int i=1;i<=n;i++){l=1,r=m;while(l<=r){mid=l+r>>1;t=a[i]*b[mid];if(t<=x)cnt+=mid-l+1,l=mid+1;else r=mid-1;if(cnt>=k)return cnt;}}return cnt;
}int main(){freopen("sort.in","r",stdin);freopen("sort.out","w",stdout);while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=m;i++) b[i]=read();sort(a+1,a+n+1);sort(b+1,b+m+1);l=a[1]*b[1];r=a[n]*b[m];while(l<=r){mid=l+r>>1;if(check(mid)>=k)r=mid-1,ans=mid;else l=mid+1;}	printf("%d\n",ans);}
}