ミックススパイス２

調理の際、スパイスをミックスして使用すると、１種類のスパイスだけ使用したときより風味が増します。ミックススパイスは、数種類のスパイスをあらかじめ決められた比率で混ぜ合わせた調味料です。

あなたは予算の許す範囲で数種類のスパイスを購入し、できるだけ大量のミックススパイスを作ろうとしています。あなたの手元には、既にスパイスがいくらかあります。さらに、各スパイスの購入額の合計が予算を超えない範囲でいくらでも多くスパイスを買い足すことができます。こうして集めたスパイスを使って、あなたは最大でどれだけのミックススパイスを作ることができるでしょうか。

ミックススパイスに使うスパイスの種類の数と予算、各スパイスの1グラム当たりの価格、手元にある各スパイスの量、ミックススパイスの比率が与えられたとき、最大で何グラムのミックススパイスを作ることができるかを計算するプログラムを作成せよ。ただし、スパイスを購入する最小単位は1グラムとし、スパイスの調合をするときに使うことができる各スパイスの最小単位も１グラムとする。

入力

入力は以下の形式で与えられる。

$N$ $C$
$a_1$
：
$a_N$
$b_1$
：
$b_N$
$x_1$
：
$x_N$

１行目にスパイスの種類の数$N$ ($2 \leq N \leq 100$)とミックススパイスの予算$C$ ($0 \leq C \leq 10^{10}$)が与えられる。続く$N$行に、$i$番目のスパイスの1グラム当たりの価格$a_i$ ($1 \leq a_i \leq 10,000$)が整数で与えられる。続く$N$行に、手元にある$i$番目のスパイスの量$b_i$ ($0 \leq b_i \leq 10,000$)がグラム単位の整数で与えられる。続く$N$行に各スパイスの比率$x_1$:$x_2$:...:$x_N$を示す数$x_i$ ($1 \leq x_i \leq 10,000$)が与えられる。ただし、$x_1$,$x_2$,...,$x_N$の最大公約数は１であるものとする。

出力

作ることのできるミックススパイスの最大の量をグラム単位で１行に出力する。

入出力例

入力例１

2 100
2
8
5
5
1
1

出力例１

30

入力例２

3 100
10
10
10
10
10
2
2
4
3

出力例２

27

入力例３

2 10000000000
1
1
10000
10000
1
1

出力例３

10000020000

Note

Algorithm

 

---