As Mr. Shim (your favourite math teacher) always says, you control the numerator and he controls the denominator. While you may control the numerator, Mr. Shim can manipulate the denominator as he pleases, and thus controls the value. There are ~N~ students in the class, and you will be given ~N~ numerators that represents the grade of each student. You will also be given ~M~ denominators, the denominators that Mr. Shim is considering using. It is your job to choose the optimal denominator for your class in order to obtain the class average of ~X~.
There are however, a few concerning limitations! The most important one is that students are not allowed to have a grade over ~100\%~, meaning that the numerator can never be larger than the denominator. Additionally, you also cannot allow the class to fail (to have an average below ~50\%~). If no such denominators meet those limitations, then output
Shimnanigans have failed. Which denominator gives the average closest to ~X~?
~1 \leq N, M \leq 10^3~
~30 \leq X \leq 100~
The first line will contain space separated integers, ~N~, ~M~ and ~X~.
The next line will each contain ~N~ space separated integers, representing the given numerators.
The next line will each contain ~M~ space separated integers, representing the possible denominators.
Output the denominator that will place the average closest to ~X~. If no denominators are valid, then output
Shimnanigans have failed. If there are two denominators that yield equally close averages, output the larger one because you love your classmates.
Sample Input 1
3 3 100 23 31 27 27 35 32
Sample Output 1
Sample Input 2
10 1 87 7 2 3 4 3 5 11 1 2 8 1
Sample Output 2
Shimnanigans have failed