P1926 Xiao Shutong — The Problem-Grinding Army

Math is fire, lighting the lamp of physics; physics is a lamp, illuminating the road of chemistry; chemistry is a road, leading to the pit of biology; biology is a pit, burying those who study science. Classical Chinese is fire, lighting the palace lamps of history; history is a lamp, illuminating the road of society; society is a road, leading to the big pit of philosophy; philosophy is a pit, burying liberal arts students. — Xiao A.

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.

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.

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

### 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