한 배열 A[1..n] 에 대해여 부 배열은 1 <= i <= j <= n 인 A[i..j] 를 말한다.

부 배열 A[i..j] 의 합은 A[i]+ ... +A[j] 이다. 원소가 양의 정수인 두 배열 A[1..n] 와 B[1..m] 가 주어져 있다. A 의 부 배열의 합에 B 의 부 배열의 합을 더해서 t 가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를들어, A=(1,3,1,2) , B=(1,3,2) 이고 t=5 인 경우, 합이 5 가되는 A 와 B 의 부 배열의 쌍의 개수는 아래와 같다.

A[1] + B[1] + B[2]
= A[1] + A[2] + B[1]
= A[2] + B[3]
= A[2] + A[3] + B[1]
= A[3] + B[1] + B[2]
= A[3] + A[4] + B[3]
= A[4] + B[2]
= 5

입력 방법

• 첫째 줄에는 t(t <= 10000) 가 주어진다.
• 둘째 줄에는 배열 A 의 크기 n( n <= 1000) 이 주어지고,
• 셋째 줄에는 A 의 원소들이 A[1] 부터 차례대로 주어진다.
• 넷째 줄에는 배열 B 의 크기 m (m <= 1000)이 주어지고,
• 마지막 줄에는 B 의 원소들이 B[1]부터 차례대로 주어진다.

출력 방법

입출력 예

입력

5
4
1 3 1 2
3
1 3 2

출력

7

출처:koi 고등부 기출