题目描述

小珅有n种面值不同的钱币，具体地说，小珅有面值w₁的钱币c₁个，面值w₂的钱币c₂个,...,面值wₙ的钱币cₙ个。

小珅想知道用手中的钱币，恰好凑出m的方法有多少种？

输入格式

第1行两个正整数n,m,用空格分隔

第2行n个正整数w₁,w₂,…,wₙ

第3行n个正整数c₁,c₂,…,cₙ

输出格式

一个整数，恰好凑出m的方法数

3 10
1 2 4
3 3 3

4

2 1
1 8
1 3

1

2 71
23 7
5 2

0

提示

说明/提示

1≤n≤10;

1≤m,wᵢ≤10⁶，wᵢ互不相同;

1≤cᵢ≤5;

【样例说明】

小珅有面值1的3个，面值2的3个，面值4的3个，恰好凑成10的方法有以下4种:

4+4+2

4+4+1+1

4+2+2+2

4+2+2+1+1