716 . 換錢錢，但我窮
TopCoder
Tags
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
1 5 10 50 100
123 1 1 1 1
Sample Output 1
11
Sample Input 2
5 8763
1 31 124 372 4836
8763 8 7 6 5
1 31 124 372 4836
8763 8 7 6 5
Sample Output 2
601
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~17 | 無額外限制 | 100 |