# Four Arrays Codechef Solution | May CHALLENGE

Share:

Four Arrays Codechef Solution

You have been given an integer KK and four arrays AA, BB, CC, and DD with sizes SASA, SBSB, SCSC and SDSD respectively.

• Pick four indices xx, yy, zz, and ww from arrays AA, BB, CC, and DD respectively. Note that (1≤x≤SA)(1≤x≤SA), (1≤y≤SB)(1≤y≤SB), (1≤z≤SC)(1≤z≤SC) and (1≤w≤SD)(1≤w≤SD).
• There are in total SA×SB×SC×SDSA×SB×SC×SD ways to do the above step. For each way, write down the value of (Ax+By)×(Cz+Dw)(Ax+By)×(Cz+Dw) on a board.
• Sort all the numbers written on the board in non-decreasing order.

Find the KthKth element written on the board.

### Input Format

• First line contains five integers SASA, SBSB, SCSC, SDSD and KK.
• The second line contains SASA space-separated integers A1,A2,…,ASAA1,A2,…,ASA denoting the array AA.
• The third line contains SBSB space-separated integers B1,B2,…,BSBB1,B2,…,BSB denoting the array BB.
• The fourth line contains SCSC space-separated integers C1,C2,…,CSCC1,C2,…,CSC denoting the array CC.
• The fifth line contains SDSD space-separated integers D1,D2,…,DSDD1,D2,…,DSD denoting the array DD.

### Output Format

For each test case, output the required number in a single line .

### Constraints

• 1≤SA,SB,SC,SD≤3⋅1041≤SA,SB,SC,SD≤3⋅104
• 1≤K≤SA×SB×SC×SD1≤K≤SA×SB×SC×SD
• 0≤Ai,Bi,Ci,Di≤1050≤Ai,Bi,Ci,Di≤105

### Sample Input 1

``````2 1 3 2 10
2 3
2
1 1 2
3 1
``````

### Sample Output 1

``````20
``````

### Explanation

After sorting the numbers on the board are in the following order {8,8,10,10,12,15,16,16,20,20,20,25}{8,8,10,10,12,15,16,16,20,20,20,25}. So, the 10th10th number is 2020.