Square Route

Time Limit : 8 sec, Memory Limit : 65536 KB

Square Route

スクウェア・ルート

English text is not available in this practice contest.

このたび新しい豪邸を建てることを決めた大富豪の品田氏は,どの街に新邸を建てようかと悩んでいる.実は,品田氏は正方形がとても好きという変わった人物であり,そのため少しでも正方形の多い街に住みたいと思っている.

品田氏は,碁盤目状に道路の整備された街の一覧を手に入れて,それぞれの街について,道路により形作られる正方形の個数を数えることにした.ところが,道と道の間隔は一定とは限らないため,手作業で正方形を数えるのは大変である.そこであなたには,碁盤目状の道路の情報が与えられたときに,正方形の個数を数えるプログラムを書いて欲しい.

Input

入力は複数のデータセットから構成されており,各データセットは以下のような構成になっている.

N M
h1
h2
...
hN
w1
w2
...
wM

1 行目には 2 つの正の整数 N, M (1 ≦ N, M ≦ 1500) が与えられる.続く Nh1, h2, ..., hN (1 ≦ hi ≦ 1000)は,道路と道路の南北方向の間隔を表す.ここで hi は北から i 番目の道路と北から i + 1 番目の道路の間隔である.同様に,続く Mw1, ..., wM (1 ≦ wi ≦ 1000)は,道路と道路の東西方向の間隔を表す.ここで wi は西から i 番目の道路と西から i + 1 番目の道路の間隔である.道路自体の幅は十分細いため考慮する必要はない.

最初のデータセット
図 D-1: 最初のデータセット

N = M = 0 は入力の終端を示しており,データセットには含めない.

Output

各データセットに対して,正方形の個数を 1 行に出力しなさい.たとえば,Sample Input の最初のデータセットにおいては,以下のとおり 6 個の正方形を含むので,このデータセットに対する出力は 6 となる.

最初のデータセットに含まれる正方形
図 D-2: 最初のデータセットに含まれる正方形

Sample Input

3 3
1
1
4
2
3
1
1 2
10
10
10
0 0

Output for the Sample Input

6
2

Source: ACM International Collegiate Programming Contest , ACM-ICPC Japan Alumni Group Practice Contest for Japan Domestic 2007, 2007
http://acm-icpc.aitea.net/