题目描述

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

在王国中，J 公司的全自动咖啡厅出售甜点和饮品。

J 公司的全自动咖啡厅有一台出售 $N$ 个甜点的甜点自动售货机，以及一台出售 $M$ 杯饮品的饮品自动售货机。甜点编号为 $1$ 到 $N$，饮品编号为 $1$ 到 $M$。

甜点 $i$ 的价格为 $A_i$ 美元，饮品 $j$ 的价格为 $B_j$ 美元。

作为支付方式，甜点自动售货机同时接受 $1$ 美元纸币和 $K$ 美元纸币，但饮品自动售货机只接受 $K$ 美元纸币。两台自动售货机都只用 $1$ 美元纸币找零。同一种商品不能购买两个或更多。

高桥君带着 $X$ 张 $1$ 美元纸币和 $Y$ 张 $K$ 美元纸币来到了 J 公司的全自动咖啡厅。

在他用所持纸币能够购买的商品组合中，求出他最多能购买的商品数量。

输入格式

输入按以下格式从标准输入读入：

• $N$ $M$ $K$
• $X$ $Y$
• $A_1$ $A_2$ $\ldots$ $A_N$
• $B_1$ $B_2$ $\ldots$ $B_M$

输出格式

输出答案。

2 3 10
50 6
22 30
20 12 24

4

• 按如下方式购物，高桥君可以购买 4 个商品。
  • 支付两张 $10$ 美元纸币购买饮品 $1$。没有找零。
  • 支付两张 $10$ 美元纸币购买饮品 $2$。找零为八张 $1$ 美元纸币。
  • 支付两张 $10$ 美元纸币和十张 $1$ 美元纸币购买甜点 $2$。没有找零。
  • 支付二十二张 $1$ 美元纸币购买甜点 $1$。没有找零。

他无法购买超过 4 个商品，因此答案为 $4$。

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

1

• 按如下方式购物，高桥君可以购买 1 个商品。
  • 支付 $600000777666777$ 张 $1$ 美元纸币购买甜点 $1$。找零为 $600000000000000$ 张 $1$ 美元纸币。

他无法购买超过 1 个商品，因此答案为 $1$。

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

22

数据范围

• $1 \leq N \leq 2 \times 10^5$

• $1 \leq M \leq 2 \times 10^5$

• $2 \leq K \leq 10^9$

• $0 \leq X \leq 10^{15}$

• $0 \leq Y \leq 10^9$

• $1 \leq A_i \leq 10^9$（$1 \leq i \leq N$）

• $1 \leq B_j \leq 10^9$（$1 \leq j \leq M$）

• 所有输入值均为整数。

• 来源：AtCoder ABC 476 D

子任务设置

• 子任务 1（30 分）：$N,M \le 2000$ 且 $X,Y \le 2000$。
• 子任务 2（30 分）：$N,M \le 2\times 10^5$ 且 $X,Y \le 2000$。
• 子任务 3（40 分）：无特殊限制。