J17 例题-5 货币支付

题目描述

金银岛上的人使用金币，每种金币面值分别是 $A_1, A_2, A_3,..., A_n$ 元。一天猪爸爸出差经过，决定在附近商店买一个非常好的表，他想在付钱的时候不要找零，但是他发现他的钱包里每种金币的数量分别只有 $C_1, C_2, C_3,..., C_n$ 个。不过，猪爸爸 知道这块表的价格不会超过 $M$ 元金币（他不知道表的精确价格）。请帮助猪爸爸算一下，在 $1$ 到 $M$ 元范围内（包括边界），他钱包中的金币可以精确支付多少种价格。

输入格式

每个测试点的格式如下： 第一行包括 $2$ 个整数 $n, M$。 第二行包括 $n$ 个整数 $A_1, A_2, A_3,..., A_n$； 第三行包含 $n$ 个整数 $C_1, C_2, C_3,..., C_n$ 。

输出格式

输出一行，为一个整数，即能精确支付的价格种数。

样例输入

3 10
1 2 4 
2 1 1

样例输出

8

样例分析

如上所述。

数据范围

$100\%$ 的数据：$1 \leq n \leq 100, 1 \leq M \leq 10000, 1\leq A_i,C_i \leq 1000$。