Problem Description

People in Silverland use coins. They have coins with denominations $A_1, A_2, A_3, \dots, A_n$. One day, Tony opened his piggy bank and found some coins inside. He decided to go to a nearby shop to buy a very nice watch. He wants to pay the exact price (no change), and he knows the price of the watch will not exceed $m$. However, he does not know the exact price of the watch.

You need to write a program that reads $n$, $m$, $A_1, A_2, A_3, \dots, A_n$, and the corresponding counts $C_1, C_2, C_3, \dots, C_n$ (which means how many coins of each denomination Tony has), and then computes how many prices Tony can pay using these coins (all prices from $1$ to $m$).

Input Format

The input contains multiple test cases (no more than $25$ cases). The first line of each test case contains two integers $n$ $(1 \le n \le 100)$ and $m$ $(m \le 100000)$. The second line contains $2n$ integers, which represent $A_1, A_2, A_3, \dots, A_n$ and $C_1, C_2, C_3, \dots, C_n$ $(1 \le A_i \le 100000, 1 \le C_i \le 1000)$. The last test case ends with two zeros.

Output Format

For each test case, output the answer on a separate line.

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

8
4

Hint

Translated by ChatGPT 5