题目描述

在 AtCoder 王国，流通着 $1$ 元纸币和 $K$ 元纸币两种纸币。

王国里 J 公司的全自动食堂出售甜点和饮料。食堂有一台卖 $N$ 种甜点的甜点售货机和一台卖 $M$ 种饮料的饮料售货机。甜点编号 $1$ 到 $N$，饮料编号 $1$ 到 $M$。

甜点 $i$ 的价格是 $A_i$ 元，饮料 $j$ 的价格是 $B_j$ 元。

支付时：甜点售货机同时接受 $1$ 元和 $K$ 元纸币，而饮料售货机只接受 $K$ 元纸币。两台售货机找零时都只用 $1$ 元纸币。同一种商品不能买两个及以上。

高橋君带着 $X$ 张 $1$ 元纸币和 $Y$ 张 $K$ 元纸币来到食堂。

请求出他用手上的纸币能买到的商品数量的最大值。

输入格式

N M K
X Y
A_1 ... A_N
B_1 ... B_M

输出格式

输出答案。

输入示例 1

2 3 10
50 6
22 30
20 12 24

输出示例 1

4

示例 1 说明

按下面的方式购买可以买到 $4$ 件商品：

• 付 $2$ 张 $10$ 元买饮料 $1$（$20$ 元），无找零；
• 付 $2$ 张 $10$ 元买饮料 $2$（$12$ 元），找回 $8$ 张 $1$ 元；
• 付 $2$ 张 $10$ 元和 $10$ 张 $1$ 元买甜点 $2$（$30$ 元），无找零；
• 付 $22$ 张 $1$ 元买甜点 $1$（$22$ 元），无找零。

买不到 $5$ 件，所以答案是 $4$。

注意找回的 $1$ 元纸币可以继续用来买甜点，所以钱其实一分没浪费。

输入示例 2

1 7 67
677677677766666 0
777666777
20 12 24 67 67 67 67

输出示例 2

1

示例 2 说明

$Y = 0$，一张 $K$ 元纸币都没有，而饮料售货机只收 $K$ 元纸币，所以一瓶饮料都买不了。甜点可以用 $1$ 元纸币买，$X$ 足够买下唯一的那种甜点，答案是 $1$。

这组数据用来检验「没有 $K$ 元纸币时饮料全部不可买」这个边界。

输入示例 3

20 20 30
605776135 133105105
97363214 218434035 697895427 109255624 299037330 227873982 195540071 411713803 828357845 244535208 138059186 639510883 39844882 707397687 371274487 696536603 351588202 319490007 47121612 87169661
32256972 567982330 554885983 299718223 443859449 687952877 264684780 666659381 576335424 941894234 406248934 321334900 423472560 863738035 213143887 384834384 468161291 673106162 164648316 15903323

输出示例 3

22

示例 3 说明

$N = M = 20$，答案 $22$ 说明两种商品都买了不少。这组数据里 $X$、$Y$、$A_i$、$B_j$ 都接近 $10^9$ 量级，总金额 $X + Y \times K$ 接近 $4 \times 10^9$，已经超出 $32$ 位整数范围，可用来检验是否使用了 long long。

约束条件

• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $2 \le K \le 10^9$
• $0 \le X \le 10^{15}$
• $0 \le Y \le 10^9$
• $1 \le A_i \le 10^9 \ (1 \le i \le N)$
• $1 \le B_j \le 10^9 \ (1 \le j \le M)$
• 所有输入值均为整数