Migrated from Lutece 2836 Rather Easy Problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Since few members in the training zoo would like to contribute problems to the UESTCPC 2077 Preliminary (almost all of them participate in it...), Kanade had to forcefully assign them the task of contributing problems.

Kanade found $m$ tool people and asked them to contribute problems. But she didn't tell them how many problems were needed. She intended them to guess the number. She told to the $i$-th person that if the problems were divided into groups of $b_i$, then $a_i$ problem(s) would be left.

The $m$ tool people gathered together. They knew that there wouldn't be more than $n$ problem(s) according to the restriction of DOMjudge. Let the number of problems needed be $x$. They would like to know how many $x$ meets the conditions Kanade told to them.

Please note that at least one problem is needed for organizing the contest. And Kanade was kind enough that she didn't tell any wrong conditions to the tool people. But it seems that she doesn't realize that DOMjudge has a restriction on the number of problems.

Input

The first line contains two integers $n,m\ (1\le n\le 10^9,1\le m\le 10)$, indicating the maximum problems that can be set on DOMjudge and the number of tool people.

The second line contains $m$ integers $b_1,b_2,\ldots b_m\ (1\le b_i\le 10)$.

The third line contains $m$ integers $a_1,a_2,\ldots ,a_m\ (0\le a_i<b_i)$.

Output

Output an integer in one line, indicating the number of $x$ which meets the conditions Kanade told to the tool people.

Samples

114 3
8 9 3
5 4 1

2

Note

Only $13$ and $85$ meet the conditions.

Resources

The 18th UESTC Programming Contest Preliminary