4120 - 【提高组】第五课:凑硬币

有n种面值的硬币,面值分别为$ a_1, a_2,..., a_n $,数量分别为$ c_1, c_2, c_3,..., c_n $,请问在这些硬币的组合下,能够组成多少种不超过m的面值。

输入

第一行输入两个整数$ n, m (1 \le n \le 100, 1 \le m \le 10^5 )$。

第二行有n个整数$ a_1, a_2, a_3,... , a_n (0 \le a_i \le 10^5)$。

第三行有n个整数$ c_1, c_2, c_3,... , c_n (0 \le c_i \le 1000 )$。

输出

输出一个整数,表示答案。

样例

输入

3 10
1 2 4
2 1 1

输出

8

输入

2 5
1 4
2 1

输出

4

提示

子任务1,20分,$ 1 \le n \le 10, 1 \le m \le 10^5 $,$ 0 \le a_i \le 10^5 $,$ c_i = 1 $。

子任务2,30分,$ 1 \le n \le 100, 1 \le m \le 10^5 $,$ 0 \le a_i \le 10^5 $,$ c_i = 1 $。

子任务3,50分,全范围。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题