题目描述

伞伞正在厨房研发新的菜品。厨房共有 $n$ 种食材，第 $i$ 种食材有 $a_i$ 个。伞伞每研发一道菜品，需要消耗第 $i$ 种食材 $b_i$ 个，除此之外，伞伞还有 $k$ 包 “魔法粉”。每包魔法粉都可以变成任意种类的食材。消耗 $1$ 包魔法粉可以获得 $c$ 个相同种类的食材。现在伞伞想知道，他最多可以研发多少道菜品。

输入格式

从文件 dish.in 读入数据。 第一行包含三个整数 $n,k,c$，表示食材数、魔法粉数、消耗一包魔法粉可以获得的食材数量。

接下来一行 $n$ 个整数 $a_i$，表示厨房里第 $i$ 种食材的数量。

接下来一行 $n$ 个整数 $b_i$，表示研发一道菜品需要消耗第 $i$ 种食材的数量。

输出格式

输出到文件 dish.out。 一行一个整数，表示最多可以研发多少道菜品。

样例

3 1 1
11 3 16
2 1 4

4

4 3 1
11 12 14 20
4 3 5 6

3

4 3 6
11 12 14 20
4 3 5 6

4

1 1000000000 1000000000
1
1

1000000000000000001

3 10 2
10 20 30
3 5 7

5

样例 6&10

见下发文件。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 2 \times 10^5,1 \leq k,c,a_i,b_i \leq 10^9$。

提示

答案可能超过 $10^9$。