题目描述珅泽教育的小珅同学有n种面值不同的钱币具体地说小珅有面值w1的钱币c1个面值w2的钱币c2个面值wn的钱币cn个小珅想知道用手中的钱币恰好凑出m的方法有多少种输入第1行两个正整数nm用空格分隔第2行n个正整数w1w2⋯wn第3行n个正整数c1c2⋯cn

输入样例 4 10 1 2 5 10 5 3 2 1

输出样例 11

说明 小珅可以用面值为1的钱币凑出10，也可以用面值为2的钱币凑出10，依此类推，共有11种凑法。

提示 可以使用动态规划来解决这个问题。设dp[i][j]表示使用前i种面值的钱币凑出金额j的方法数。那么对于第i种面值的钱币，有两种情况：不使用这种面值的钱币，那么dp[i][j] = dp[i-1][j]；使用至少一枚这种面值的钱币，那么dp[i][j] = dp[i][j-wi] + dp[i-1][j]。最终的答案为dp[n][m]。