You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

luogu P1926

2022-2023春季学期初一信息竞赛组期中考第一题

Description

小A是信息组的同学，今天他在hfoj找到了$n$道想做的编程题，他对自己的实力非常清楚，知道自己做第$i$题的时间$a_i$。但是，老师今天也布置了$m$道作业题，做完第j个作业题需要用时$t_j$，能获得$v_j$的分数。小A今天只剩$r$单位的时间了，他想在作业及格的基础上尽可能多刷几个编程题，问小A最多可以刷多少个编程题。

Format

Input

输入第一行四个正整数为小A想刷的题的数量$n$，老师布置的作业题数量$m$，作业所需的及格分数$k$，以及小A今天剩下的时间$r$。

第二行$n$个正整数为小A刷每道编程题的时间$a_i$。

第三行$m$个正整数为小A做每个作业题的时间$t_i$。

第四行$m$个正整数为每个作业题的分数$v_i$。

Output

一个正整数表示小A最多可以刷多少编程题。

Samples

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

2

Limitation

对$30\%$的数据，$n≤10,m≤10,k≤50,r≤150$；

对$100\%$的数据，$n≤10​^5​,m≤500,k≤10​^5​,r≤10^5$。