Exact Coin Payment

Tony from Silver Nation has a collection of coins with denominations \(A_1, A_2, \dots, A_n\) and corresponding counts \(C_1, C_2, \dots, C_n\). One day, he decides to buy a beautiful watch whose price is at most \(m\). Since he wants to pay the exact amount (without needing change), your task is to determine how many prices from 1 to \(m\) can be exactly paid using the coins he possesses.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(m\): the number of coin types and the maximum price, respectively.
2. The second line contains \(n\) integers \(A_1, A_2, \dots, A_n\), representing the coin denominations.
3. The third line contains \(n\) integers \(C_1, C_2, \dots, C_n\), representing the number of coins available for each denomination.

outputFormat

Output a single integer: the number of distinct prices between 1 and \(m\) (inclusive) that can be exactly paid using the available coins.

sample

3 10
1 2 5
2 1 1

9