Pizza Sales

A customer wants to order pizza from a shop that sells two kinds of pizza, A and B. Each pizza has already been cut into several pieces, and the number written on each piece is its size.

When the customer states the desired total size, the shop may sell pieces from pizza A only, from pizza B only, or from both pizzas. If the shop sells two or more pieces from one pizza, those pieces must be consecutive around that pizza. The sum of all sold pieces must be exactly the requested size.

For example, with the pizzas shown in <Figure 1>, if the customer orders total size 7, the shop can sell pizza in 5 different ways as shown in <Figure 2>.

Write a program that computes the number of all possible ways to sell pizza of the requested size.

The first line contains the desired pizza size K. K is a natural number not greater than 2,000,000.

The second line contains two integers m and n, the number of pieces in pizzas A and B, respectively. 3 <= m, n <= 1000.

The next m lines contain the sizes of the pieces of pizza A in clockwise order. The following n lines contain the sizes of the pieces of pizza B in clockwise order. Each piece size is a natural number not greater than 1000.

Print one integer: the number of ways to sell pizza of the requested size. If there is no such way, print 0.