生产某种产品需要 N 个编号为 1,2,…,N 的工序。

对于每道工序 i ，有两种类型的机器 S i ​ 和 T i ​ 可供选择。

机器 S i ​ ：每台每天可处理 A i ​ 个产品，单价为 P i ​ 日元。 机器 T i ​ ：每台每天可加工 B i ​ 种产品，单价为 Q i ​ 日元。 您可以购买任意数量的机器，有可能是零。

假设引入机器后，工序 i 每天可以处理 W i ​ 个产品。 在此，我们将生产能力定义为 W 的最小值，即 i=1 min N ​ W i ​ 。

在总预算为 X 日元的情况下，求可实现的最大生产能力。

1<=N<=100 1<=ai,bi<=100 1<=pi,qi,x<=10000000

样例输入 3 22 2 5 3 6 1 1 3 3 1 3 2 4 样例输出 4