题目描述

青蛙老师有三个长度为 $n$ 的数组 $a,b,c$。

给定一个正整数 $k$，他想知道在所有 $n^2$ 个二元组 $(i,j)(1\le i\le n,1\le j\le n)$ 中，$a_j+b_j\times c_i$ 的第 $k$ 小值是多少。

但是他不会做，于是将问题交给你了。

输入格式

第一行一个正整数 $n$，表示数组长度。

第二行 $n$ 个正整数，依次表示 $a_1,a_2,\cdots a_n$。

第三行 $n$ 个正整数，依次表示 $b_1,b_2,\cdots b_n$。

第四行 $n$ 个正整数，依次表示 $c_1,c_2,\cdots c_n$。

接下来一行，一个正整数 $k$，含义如题所述。

输出格式

一行一个整数表示答案。

大样例:query.zip

样例输入

5
1 3 6 4 1
3 8 9 2 6
5 6 5 3 2
10

样例输出

16

数据范围

对于 $16\%$ 的数据，满足 $n\le 100,1\le a_i,b_i,c_i\le 1000$。

对于另外 $16\%$ 的数据，满足 $n\le 1000$。

对于另外 $16\%$ 的数据，满足 $k\le n,1\le a_i,b_i,c_i\le 1000$。

对于另外 $24\%$ 的数据，满足 $k\le n$。

对于 $100\%$ 的数据，满足 $n\le 10^5, 1\le k\le n^2, 1\le a_i,b_i,c_i\le 10^9$。