TopCoder

jackhuang

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Description

卡加布列島上發行的硬幣有 $N$ 種，分別價值 $A_1, A_2, \cdots, A_N$ 塊，已知 $1 = A_1 < A_2 < \cdots < A_N$，而且對於所有可能的 $i$，$A_i$ 是 $A_{i+1}$ 的因數。

學姐這次帶了價值 $K$ 塊錢的遊戲王卡去卡加布列島想要換成現金，她一樣希望拿到的硬幣越少越好。作為收銀員的你，這次每個硬幣的數量都只有 $C_i$ 個可以給學姐換錢，不然你會被老闆罵。這次你能滿足學姐的需求嗎？

因為這裡的最小硬幣是 $1$ 塊錢而且你可以給學姐的 $1$ 塊錢有 $K$ 個，所以一定有辦法換錢，不用考慮無解的狀況。

Input Format

輸入有兩行，第一行包含兩個正整數 $N, K$，代表硬幣的種數和遊戲王卡的價值。
第二行則有 $N$ 個正整數 $1 = A_1, A_2, \cdots ,A_N$，分別代表硬幣的價值，保證輸入的數字從小到大排列。
第三行則有 $N$ 個正整數 $1 = C_1, C_2, \cdots ,C_N$，分別代表硬幣的數量。

$1 \le N \le 10$
$1 \le K \le 10^ {12}$
$1 \le A_i \le 10^ {12}$, $\forall$ $i$
$1 = A_1 < A_2 < \cdots < A_N$
$A_i | A_{i+1}$, $\forall$ $i < N$
$C_1 = K$
$1 \le C_i \le 10^ 9 \forall i > 1$

其中保證一定有解，不會發生湊不出來的狀況。

Output Format

輸出一個正整數，代表需要的最少硬幣數量。

Sample Input 1

5 123
1 5 10 50 100
123 1 1 1 1

Sample Output 1

Sample Input 2

5 8763
1 31 124 372 4836
8763 8 7 6 5

Sample Output 2

601

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0~1	範例測資	0
2	0~17	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	1 2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2
16	1000	524288	65536	2
17	1000	524288	65536	2

716 . 換錢錢，但我窮