VM 09 Bài 05 - Nuga chia kẹo

View as PDF

Submit solution

Points: 1.38 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon 2009Round 4Problem Setter: Phạm Lê Quang
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

image

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

Comments

Please read the guidelines before commenting.



  • 0
    karrigan   commented on June 25, 2022, 11:59 a.m.

    cho em hỏi bài này có cần dùng bignum để ac không ạ ?