Description

Xiao A is wildly “grinding problems”, blatantly “grinding problems”. He has found $n$ kinds of “problems” he likes in Xiao Shutong, and each “problem” has a required time. The teacher has assigned $m$ homework tasks, each with its required time and score, and the teacher stipulates that $k$ points or more is passing. Xiao A has only $r$ units of time left, and he wants to “grind” as many “problems” as possible on the basis of passing.

Input Format

The first line contains four integers $n,m,k,r$.

The second line has $n$ numbers, representing the required time for each “problem”.

The third line has $m$ numbers, representing the required time for each homework task.

The fourth line has $m$ numbers, representing the score of each homework task.

Output Format

A single number, representing how many “problems” Xiao A can grind.

3 4 20 100
15 20 50
10 15 40 40
5 5 10 15

2

Hint

Constraints and Agreements

For $100\%$ of the testdata, $n\le 10$, $m\le 10$, $k\le 50$, $r\le 150$. It is guaranteed that passing is always possible.

Translated by ChatGPT 5