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

Mid-Fall Festival is coming, Nuga has bought a lot of candies for her sisters and brothers. Nuga has M candies in total, and she wants to give all of them to N children. We number the children from 1 to N.

Nuga knows that the i-th child is happy only if he or she get at least A_i candies. However one’s parents don’t want their child to eat more than B_i candies (to avoid dental caries). So, Nuga has to give the i-th child X_i candies that satisfies A_i ≤ X_i ≤ B_­i.

Please help Nuga to calculate how many ways that she can divides M candies among N children and satisfy all conditions.

Input

- The first line contains 2 integers M, N.

- The second line contains N integers A₁, A₂, …, A_n.

- The third line contains N integers B₁, B₂, …, B_n. 

Constraint

- In 30% of the test cases, 1 ≤ N ≤ 5 và 0 ≤ A_i ≤ B_i ≤ M ≤ 20.

- In other test cases, 1 ≤ N ≤ 16 và 0 ≤ A_i ≤ B_i ≤ M ≤ 10⁹.

Output

One line contains the number of satisfied ways.

Example

Input: 
6 3
0 0 0
3 2 4

Output:
9