Jen likes playing with lists of nonzero integers. She has many such lists in her almirah. To kill her boredom, she would take some list and look for the smallest number in it.
However, she soon lost interest in doing so because it was too easy, so she decided to create a new list using this procedure:
-- lists are 1-indexed --
procedure generate_list(A, B, x):
let n = length of A
let m = length of B
let L = an empty list
for i from 1 to min(n, m - x), inclusive:
for j from (i + x) to m, inclusive:
Append (A[i]*B[j]) to the end of L
return L
To create , she takes two lists and and an integer and calls generate_list(A, B, x). She was surprised to see such a big list and got stuck on finding the smallest number in it. Can you help her?
Note: The smallest number in a list is the element of when it is sorted. For example, the smallest number in is .
Input Format
The first line contains four space-separated integers , , and . and are the respective sizes of and .
The second line contains space-separated integers .
The third line contains space separated integers .
Constraints
Subtasks
- for of the maximum score.
Output Format
Print a single line containing a single integer denoting the answer: the smallest number in the list .
Sample Input 0
3 4 1 5
2 -3 1
3 1 -2 -1
Sample Output 0
3
Explanation 0
is obtained from generate_list([2, -3, 1], [3, 1, -2, -1], 1). We find that . Therefore, the smallest number in is .