한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, \(1 \le i \le j \le n)\)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 \(A = {1,\) 3, 1, 2}, \(B = {1,\) 3, 2}, \(T=5\)인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

\(T(=5) = 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]

※ 이 문제의 채점 데이터는 공개된 공식 데이터가 없어 재구성한 것입니다. 문제 지문은 원본(정보올림피아드 기출)을 따릅니다.

첫째 줄에 \(T(-1{,}000{,}000{,}000 \le T \le 1{,}000{,}000{,}000)\)가 주어진다. 다음 줄에는 \(n(1 \le n \le 1{,}000)\)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 \(m(1 \le m \le 1{,}000)\)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2001 > 2차 대회 > 고등부 1번