655. Target Adarsh

0

Medium

Adarsh is in need of a specific amount of money. He has asked each of his N friends to contribute. Each friend possesses a unique coin and can contribute an unlimited number of that coin. Your task is to assist Adarsh in determining the number of distinct ways he can collect coins from his friends in order to reach the target sum.

It is guaranteed that the number of unique combinations that sum up to the target is less than 5550 combinations for the given input.

It is guaranteed that the number of unique combinations that sum up to the target is less than 5550 combinations for the given input.

Input Format

The first line contains an integer N, representing the number of friends and the target amount.

The second line contains N distinct integers, representing the value of each friend's coin.

The second line contains N distinct integers, representing the value of each friend's coin.

Output Format

Print the total number of unique ways Adarsh can collect money from his friends that sum up to the target value.

Example

Input

4 7
2 3 6 7

Output

2

Constraints

1<=N<=30

1<=Coin’s value<=200

1<=target<=500

1<=Coin’s value<=200

1<=target<=500

Loading...

View Submissions

Console