Tết Trung Thu sắp đến và chị Nuga đã mua rất nhiều kẹo để chia cho các em của mình. Tổng số Nuga có ~M~ chiếc kẹo và cần chia hết cho ~N~ em. Để cho tiện, ta đánh số các em từ ~1~ đến ~N~.

Nuga biết rằng em thứ ~i~ chỉ vui khi nhận được ít nhất ~A_{i}~ cái kẹo. Nhưng bố mẹ của em ấy cũng không muốn con mình ăn quá ~B_{i}~ chiếc (để tránh sâu răng). Như thế, Nuga phải chia cho em thứ ~i~ số kẹo là ~X_{i}~ thỏa mãn ~A_{i} \leq X_{i} \leq B_{­i}~.

Bạn hãy giúp Nuga tính xem có bao nhiêu cách chia ~M~ chiếc kẹo cho ~N~ em để thỏa mãn tất cả các yêu cầu trên.

Input

• Dòng đầu ghi ~2~ số nguyên ~M~, ~N~.
• Dòng thứ hai gồm ~N~ số nguyên ~A_{1}~, ~A_{2}~, ..., ~A_{n}~.
• Dòng thứ ba gồm ~N~ số nguyên ~B_{1}~, ~B_{2}~, ..., ~B_{n}~.

Output

• Một dòng duy nhất chứa số cách chia thỏa mãn.

Giới hạn

• Trong ~30\%~ tổng số test, ~1 \leq N \leq 5~ và ~0 \leq A_{i} \leq B_{i} \leq M \leq 20~.
• Trong các test còn lại, ~1 \leq N \leq 16~ và ~0 \leq A_{i} \leq B_{i} \leq M \leq 10^{9}~.

Sample Input

6 3
0 0 0
3 2 4

Sample Output

9