Sum of Subarrays from Two Arrays

For an array A[1], A[2], ..., A[n], a contiguous subarray is A[i], A[i+1], ..., A[j] where 1 <= i <= j <= n. Its sum is A[i] + ... + A[j].

Given two integer arrays A[1], ..., A[n] and B[1], ..., B[m], count the number of pairs made of one contiguous subarray from A and one contiguous subarray from B such that their sums add up to T.

sum(A[i..j]) + sum(B[p..q]) = T

The first line contains T (-1,000,000,000 <= T <= 1,000,000,000).

The next line contains n (1 <= n <= 1,000), followed by a line containing n integers A[1], ..., A[n].

The next line contains m (1 <= m <= 1,000), followed by a line containing m integers B[1], ..., B[m].

Every array element is an integer whose absolute value is at most 1,000,000.

Print the answer on the first line. If there is no valid pair, print 0.