Giải bài trực tuyến

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 ≤ X_i ≤ 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.

Dữ liệu

- Dòng đầu ghi 2 số nguyên M, N.

- Dòng thứ hai gồm N số nguyên A₁, A₂, …, A_n.

- Dòng thứ ba gồm N số nguyên B₁, B₂, …, B_n. 

Giới hạn

- Trong 30% tổng số test, 1 ≤ N ≤ 5 và 0 ≤ A_i ≤ B_i ≤ M ≤ 20.

- Trong các test còn lại, 1 ≤ N ≤ 16 và 0 ≤ A_i ≤ B_i ≤ M ≤ 10⁹.

Kết quả

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

Ví dụ

Dữ liệu:
6 3
0 0 0
3 2 4

Kết quả:
9