#BT02. 乘积陈列室

乘积陈列室

乘积陈列室

陈列室里有两排标签,第一排写着 nn 个正整数 a1,…,ana_1,\ldots,a_n,第二排写着 mm 个正整数 b1,…,bmb_1,\ldots,b_m。

从每一排各选一个标签,把两个数相乘。每一对标签的位置都会产生一张乘积卡片,因此共有 nmnm 张卡片。即使卡片上的数字相同,它们也分别计数。

将所有卡片按数字从小到大排列,请求出第 kk 张卡片上的数字。

输入格式

第一行包含三个整数 n,m,kn,m,k。

第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n。

第三行包含 mm 个整数 b1,…,bmb_1,\ldots,b_m。

输出格式

输出一个整数,表示第 kk 小的乘积。

样例 1

3 3 5
2 3 3
1 2 5
6

九张卡片排序后为 2,3,3,4,6,6,10,15,152,3,3,4,6,6,10,15,15。

样例 2

2 2 3
1000000000 1
1000000000 2
2000000000

数据范围

  • 1≤n,m≤200 0001\le n,m\le 200\,000。
  • 1≤k≤nm1\le k\le nm。
  • 1≤ai,bj≤1091\le a_i,b_j\le10^9。