stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef pair<ll,ll> pll;

ll mod=1e9+7;



//2e5

const ll max_n = 1<<18;

const ll init_m=1e18;

ll leaf_n;

vector<ll> dat(max_n);



// 要素数決定、(1<<31)-1で初期化

void init(ll n) {

  leaf_n=1;

  while(leaf_n<n) leaf_n*=2;

  for(ll i=0;i<2*leaf_n-1;i++) dat[i]=init_m;

}



// from 0 [k]->a

void update(ll k,ll a) {

  k+=leaf_n-1;

  dat[k]=a;

  while(k>0) {

    k=(k-1)/2;

    dat[k]=min(dat[k*2+1],dat[k*2+2]);

  }

}



// (a,b,0,0,leaf_n),[a,b),[0,leaf_n)

ll find(ll a, ll b, ll k, ll l, ll r) {

  if(r<=a||b<=l) return init_m;

  if(a<=l&&r<=b) return dat[k];

  else {

    ll vl=find(a,b,k*2+1,l,(l+r)/2);

    ll vr=find(a,b,k*2+2,(l+r)/2,r);

    return min(vl,vr);

  }

}



int main() {

  ll n,x;

  cin >> n >> x;

  init(n);

  for(ll i=0;i<n;i++) {

    ll a;

    cin >> a;

    update(i,a);

  }

  ll ans=1e18;

  for(ll i=0;i<n;i++) {

    ll tans=x*i;

    for(ll j=0;j<n;j++) {

      ll f=j-i;

      if(f<0) {

        f+=n;

        tans+=min(find(f,n,0,0,leaf_n),find(0,j+1,0,0,leaf_n));

      }

      else {

        tans+=find(f,j+1,0,0,leaf_n);

      }

    }

    ans=min(ans,tans);

  }

  cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 3.0972600593328665x):
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<ll> vec;

typedef vector<vec> mat;

typedef pair<ll,ll> pll;

const ll mod=1e9+7;

//const ll mod=998244353;

const ll inf=1LL<<61;



int main() {

  ll n,x;

  cin >> n >> x;

  vec a(n);

  for(ll i=0;i<n;i++) cin >> a[i];

  vec b(n,inf);

  ll ans=inf;

  for(ll i=0;i<n;i++) {

    ll tans=0;

    for(ll j=0;j<n;j++) {

      b[j]=min(b[j],a[(j-i+n)%n]);

      tans+=b[j];

    }

    tans+=i*x;

    ans=min(ans,tans);

  }

  cout << ans << endl;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>

#include <iomanip>

#include <vector>

#include <map>

#include <cmath>

#include <queue>

#include <utility>

#include <functional>

#include <deque>

#include <cctype>

#include <stack>

#include <bitset>



using ll = long long;

typedef unsigned long long ull;

typedef std::pair<ll, ll>P;

struct edge { ll to, cost; };

std::vector<edge>v[100010], w[100010];

typedef std::vector<std::vector<int>>ma;



ll min(ll a, ll b) {

	if (a >= b)return b;

	else return a;

}

ll max(ll a, ll b) {

	if (a >= b)return a;

	else return b;

}

ll gcd(ll a, ll b) {

	if (b == 0) return a;

	return gcd(b, a%b);

}

ll lcm(ll a, ll b) {

	ll g = gcd(a, b);

	return a / g * b;

}



const ll Z = 1000000007;

const ll INF = 1 << 30;

const ll INF2 = 9000000000000000000LL;

bool fl = true;

bool f = true;

int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

std::string abc = "abcdefghijklmnopqrstuvwxyz";



int main() {

	ll n, x, a[10000], d[10000], ans = INF2;

	std::cin >> n >> x;

	for (int i = 0;i < n;i++) {

		std::cin >> a[i];

		a[i + n] = a[i];

		d[i] = INF;

	}

	for (int i = 0;i < n;i++) {

		ll cost = x*i;

		for (int j = 0;j < n;j++) {

			d[j] = min(d[j], a[j + n - i]);

			cost += d[j];

		}

		ans = min(ans, cost);

	}

	std::cout << ans << std::endl;

}

// Faster C++ solution for the same problem (measured speedup: 6.423311465289299x):
#include <iostream>

#include <algorithm>

#include <cmath>

#include <map>

#include <vector>

#include <queue>

#include <functional>

#include <string>

#include <stack>

#include <set>

#include <sstream>

#include <iomanip>

#include <limits>

using namespace std;

using ll = long long;

typedef unsigned long long ull;

typedef pair<ll, ll> P;

typedef pair<ll, pair<ll, ll>> PP;



const ll MOD = 1e9 + 7;

const ll MOD2 = 998244353;

const ll INF = 1 << 30;

const ll INF2 = 9e18;

const double INF3 = 9e14;

const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };

const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };

#define ALL(x) (x).begin(),(x).end()

#define pb push_back

#define fr first

#define sc second







int main() {

	ll n, x, a[4010], ans = INF2, d[4010];

	cin >> n >> x;

	for (int i = 0;i < n;i++)cin >> a[i], a[i + n] = a[i], d[i] = INF2;

	for (int i = 0;i < n;i++) {

		ll sum = 0;

		for (int j = 0;j < n;j++) {

			d[j] = min(d[j], a[j + n - i]);

			sum += d[j];

	    }

		ans = min(ans, sum + i * x);

	}

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

const int MAXN = 2e3 + 2;

ll n, x, cost[MAXN], rmq[MAXN][20];

ll ans, dp[MAXN][MAXN];



void prep()

{

    for(int i = 0;i < n;i++)

        rmq[i][0] = cost[i];



    for(int i = 1;(1 << i) <= n;i++)

        for(int j = 0;j + (1 << (i - 1)) < n;j++)

            rmq[j][i] = min( rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1] );

}



int get_min(int l, int r)

{

    if(l > r)swap(l, r);



    int k = log2(r - l + 1);

    return min( rmq[l][k], rmq[r - (1 << k) + 1][k] );

}



int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);



    cin >> n >> x;

    for(int i = 0;i < n;i++)

        cin >> cost[i];



    prep();



    for(int r = 0;r < n;r++)

    {

        for(int i = 0;i < n;i++)

        {

            ll mn1, mn2; mn1 = mn2 = INT_MAX;



            if(i - r < 0)

            {

                mn1 = get_min(0, i);

                mn2 = get_min((i - r + n) % n, n - 1);

            }else{

                mn1 = get_min(i - r, i);

            }

            if(i == 0)

                dp[i][r] += 1LL * min(mn1, mn2);

            else

                dp[i][r] += dp[i - 1][r] + 1LL * min(mn1, mn2);

        }

    }



    ans = 99999999999999999;

    for(int i = 0;i < n;i++)

    {

        ll nval = dp[n - 1][i] + 1LL * i * x;

        ans = min(ans, nval);

    }

    cout << ans << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.283100312384208x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 2000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

int N;

LL b[MAXN+5],a[MAXN+5],x;

int main()

{

//	freopen("slime.in","r",stdin);

//	freopen("slime.out","w",stdout);

	scanf("%d %lld",&N,&x);

	for(int i=0;i<N;i++)

		scanf("%lld",&a[i]);

	fill(b,b+N,INF);

	LL ans=INF;

	for(int mv=0;mv<N;mv++)

	{

		LL ansn=0;

		for(int i=0;i<N;i++)

			b[i]=min(b[i],a[(i-mv+N)%N]);

		for(int i=0;i<N;i++)

			ansn+=b[i];

		ansn+=mv*x;

		ans=min(ans,ansn);

	}

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;typedef long long ll;

int n,x;

int a[2001],b[2001];

ll Ans;

int main(){

	scanf("%d%d",&n,&x);

	F(i,1,n) scanf("%d",a+i), Ans+=a[i], b[i]=a[i];

	F(i,1,n-1){

		ll sum=0;

		swap(a,b);

		F(j,1,n) b[j]=min(b[j],a[(j+n-2)%n+1]), sum+=b[j];

		Ans=min(Ans,sum+(ll)i*x);

	} printf("%lld",Ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.166629191905557x):
#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 2000

#define INF 1000000000000000000LL

using namespace std;

typedef long long LL;

int N;

LL b[MAXN+5],a[MAXN+5],x;

int main()

{

//	freopen("slime.in","r",stdin);

//	freopen("slime.out","w",stdout);

	scanf("%d %lld",&N,&x);

	for(int i=0;i<N;i++)

		scanf("%lld",&a[i]);

	fill(b,b+N,INF);

	LL ans=INF;

	for(int mv=0;mv<N;mv++)

	{

		LL ansn=0;

		for(int i=0;i<N;i++)

			b[i]=min(b[i],a[(i-mv+N)%N]);

		for(int i=0;i<N;i++)

			ansn+=b[i];

		ansn+=mv*x;

		ans=min(ans,ansn);

	}

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

const int MAXN = 2e3 + 2;

ll n, x, cost[MAXN], rmq[MAXN][20];

ll ans, dp[MAXN][MAXN];



void prep()

{

    for(int i = 0;i < n;i++)

        rmq[i][0] = cost[i];



    for(int i = 1;(1 << i) <= n;i++)

        for(int j = 0;j + (1 << (i - 1)) < n;j++)

            rmq[j][i] = min( rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1] );

}



int get_min(int l, int r)

{

    if(l > r)swap(l, r);



    int k = log2(r - l + 1);

    return min( rmq[l][k], rmq[r - (1 << k) + 1][k] );

}



int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);



    cin >> n >> x;

    for(int i = 0;i < n;i++)

        cin >> cost[i];



    prep();



    for(int r = 0;r < n;r++)

    {

        for(int i = 0;i < n;i++)

        {

            ll mn1, mn2; mn1 = mn2 = INT_MAX;



            if(i - r < 0)

            {

                mn1 = get_min(0, i);

                mn2 = get_min((i - r + n) % n, n - 1);

            }else{

                mn1 = get_min(i - r, i);

            }

            if(i == 0)

                dp[i][r] += 1LL * min(mn1, mn2);

            else

                dp[i][r] += dp[i - 1][r] + 1LL * min(mn1, mn2);

        }

    }



    ans = 99999999999999999;

    for(int i = 0;i < n;i++)

    {

        ll nval = dp[n - 1][i] + 1LL * i * x;

        ans = min(ans, nval);

    }

    cout << ans << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.233983182178736x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=2005,INF=0x7f7f7f7f7f7f7f7fll;

long long n,x;

long long d[MAXN][MAXN];

int main()

{

	//freopen("slime.in","r",stdin);

	//freopen("slime.out","w",stdout);

	scanf("%lld%lld",&n,&x);

	for(long long i=1;i<=n;i++)

		scanf("%lld",&d[i][0]);

	for(long long i=1;i<=n;i++)

	{

		for(long long j=1;j<n;j++)

		{

			d[i][j]=min(d[i][j-1],d[((i-j-1)+n)%n+1][0]);

		}

	}

	long long ans=INF;

	for(long long i=0;i<n;i++)

	{

		long long jans=i*x;

		for(long long j=1;j<=n;j++)

		{

			jans+=d[j][i];

		}

		ans=min(jans,ans);

	}

	printf("%lld\n",ans);

	fclose(stdin);

	fclose(stdout);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;typedef long long ll;

int n,x;

int a[2001],b[2001];

ll Ans;

int main(){

	scanf("%d%d",&n,&x);

	F(i,1,n) scanf("%d",a+i), Ans+=a[i], b[i]=a[i];

	F(i,1,n-1){

		ll sum=0;

		swap(a,b);

		F(j,1,n) b[j]=min(b[j],a[(j+n-2)%n+1]), sum+=b[j];

		Ans=min(Ans,sum+(ll)i*x);

	} printf("%lld",Ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.118594896939142x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=2005,INF=0x7f7f7f7f7f7f7f7fll;

long long n,x;

long long d[MAXN][MAXN];

int main()

{

	//freopen("slime.in","r",stdin);

	//freopen("slime.out","w",stdout);

	scanf("%lld%lld",&n,&x);

	for(long long i=1;i<=n;i++)

		scanf("%lld",&d[i][0]);

	for(long long i=1;i<=n;i++)

	{

		for(long long j=1;j<n;j++)

		{

			d[i][j]=min(d[i][j-1],d[((i-j-1)+n)%n+1][0]);

		}

	}

	long long ans=INF;

	for(long long i=0;i<n;i++)

	{

		long long jans=i*x;

		for(long long j=1;j<=n;j++)

		{

			jans+=d[j][i];

		}

		ans=min(jans,ans);

	}

	printf("%lld\n",ans);

	fclose(stdin);

	fclose(stdout);

}
// Slower C++ solution:
#include <bits/stdc++.h>



using namespace std;



typedef long long ll;

const int MAXN = 2e3 + 2;

ll n, x, cost[MAXN], rmq[MAXN][20];

ll ans, dp[MAXN][MAXN];



void prep()

{

    for(int i = 0;i < n;i++)

        rmq[i][0] = cost[i];



    for(int i = 1;(1 << i) <= n;i++)

        for(int j = 0;j + (1 << (i - 1)) < n;j++)

            rmq[j][i] = min( rmq[j][i - 1], rmq[j + (1 << (i - 1))][i - 1] );

}



int get_min(int l, int r)

{

    if(l > r)swap(l, r);



    int k = log2(r - l + 1);

    return min( rmq[l][k], rmq[r - (1 << k) + 1][k] );

}



int main()

{

	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);



    cin >> n >> x;

    for(int i = 0;i < n;i++)

        cin >> cost[i];



    prep();



    for(int r = 0;r < n;r++)

    {

        for(int i = 0;i < n;i++)

        {

            ll mn1, mn2; mn1 = mn2 = INT_MAX;



            if(i - r < 0)

            {

                mn1 = get_min(0, i);

                mn2 = get_min((i - r + n) % n, n - 1);

            }else{

                mn1 = get_min(i - r, i);

            }

            if(i == 0)

                dp[i][r] += 1LL * min(mn1, mn2);

            else

                dp[i][r] += dp[i - 1][r] + 1LL * min(mn1, mn2);

        }

    }



    ans = 99999999999999999;

    for(int i = 0;i < n;i++)

    {

        ll nval = dp[n - 1][i] + 1LL * i * x;

        ans = min(ans, nval);

    }

    cout << ans << '\n';

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.284550293109066x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll N=2005;

ll a[N];

ll d[N];

ll q[N],s,t;

ll n,x;

ll ans=1e15;

int dist(int x,int y){

    if(x<y)

        return y-x;

    return y-x+n;

}

void Solve(ll l){

    s=1,t=0;

    ll sum=1ll*x*l;

    for(ll i=n-l+1;i<=n;i++){

        while(s<=t&&a[q[t]]>=a[i])

            t--;

        q[++t]=i;

    }

    for(ll i=1;i<=n;i++){

        while(s<=t&&dist(q[s],i)>l)

            s++;

        d[i]=a[i];

        if(s<=t)

            d[i]=min(d[i],a[q[s]]);

        while(s<=t&&a[q[t]]>=a[i])

            t--;

        q[++t]=i;

        sum+=d[i];

    }

    //printf("%lld\n",sum);

    ans=min(ans,sum);

}

int main()

{

    //freopen("slime.in","r",stdin);

   // freopen("slime.out","w",stdout);

    scanf("%lld%lld",&n,&x);

    for(ll i=1;i<=n;i++)

        scanf("%lld",&a[i]);

    for(ll i=0;i<n;i++){

        Solve(i);

    }

    printf("%lld\n",ans);

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define F(i,a,b) for(int i=(a);i<=(b);++i)

using namespace std;typedef long long ll;

int n,x;

int a[2001],b[2001];

ll Ans;

int main(){

	scanf("%d%d",&n,&x);

	F(i,1,n) scanf("%d",a+i), Ans+=a[i], b[i]=a[i];

	F(i,1,n-1){

		ll sum=0;

		swap(a,b);

		F(j,1,n) b[j]=min(b[j],a[(j+n-2)%n+1]), sum+=b[j];

		Ans=min(Ans,sum+(ll)i*x);

	} printf("%lld",Ans);

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.168047206385272x):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const ll N=2005;

ll a[N];

ll d[N];

ll q[N],s,t;

ll n,x;

ll ans=1e15;

int dist(int x,int y){

    if(x<y)

        return y-x;

    return y-x+n;

}

void Solve(ll l){

    s=1,t=0;

    ll sum=1ll*x*l;

    for(ll i=n-l+1;i<=n;i++){

        while(s<=t&&a[q[t]]>=a[i])

            t--;

        q[++t]=i;

    }

    for(ll i=1;i<=n;i++){

        while(s<=t&&dist(q[s],i)>l)

            s++;

        d[i]=a[i];

        if(s<=t)

            d[i]=min(d[i],a[q[s]]);

        while(s<=t&&a[q[t]]>=a[i])

            t--;

        q[++t]=i;

        sum+=d[i];

    }

    //printf("%lld\n",sum);

    ans=min(ans,sum);

}

int main()

{

    //freopen("slime.in","r",stdin);

   // freopen("slime.out","w",stdout);

    scanf("%lld%lld",&n,&x);

    for(ll i=1;i<=n;i++)

        scanf("%lld",&a[i]);

    for(ll i=0;i<n;i++){

        Solve(i);

    }

    printf("%lld\n",ans);

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define INF 102030405060708090



// memo: 2^17 == 131072

const int MAX_N = 1 << 17; 

int n2 = 1;



vector<int> dat(MAX_N*2-1);



void init(int m) {

  while (n2 < m) n2 *= 2;



  for (int i=0;i<n2*2-1;i++) {

    dat[i] = INT_MAX;

  }

}



void update(int k, int a) {

  k += n2-1;

  dat[k] = a;

  while (k > 0) {

    k = (k-1)/2;

    dat[k] = min(dat[k*2+1],dat[k*2+2]);

  }

}



// min of [a,b)

// usage : query(a,b,0,0,n2);

int query(int a, int b, int k, int l, int r) {

  if (r <= a || b <= l) return INT_MAX;

  if (a <= l && r <= b) return dat[k];

  else {

    int vl = query(a,b,k*2+1,l,(l+r)/2);

    int vr = query(a,b,k*2+2,(l+r)/2,r);

    return min(vl,vr);

  }

}



int main() {



  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  long long x;

  cin >> n >> x;

  vector<int> a(n);

  for (int i=0;i<n;i++) cin >> a[i];



  init(n*2);

  for (int i=0;i<n;i++) {

    update(i,a[i]);

    update(n+i,a[i]);

  }



  long long ans = INF;

  for (int i=0;i<n;i++) {

    long long kans = x*i;

    for (int j=0;j<n;j++) {

      kans += query(n+j-i,n+j+1,0,0,n2);

    }

    ans = min(ans,kans);

  }

  cout << ans << endl;

}

// Faster C++ solution for the same problem (measured speedup: 2.048712579727868x):
#include <bits/stdc++.h>

using namespace std;



#define INF 102030405060708090

#define inf 1020304050



int main() {



  ios::sync_with_stdio(false);

  cin.tie(0);

  int n;

  long long x;

  cin >> n >> x;

  vector<int> a(n);

  vector<int> b(n*2);

  for (int i=0;i<n;i++) cin >> a[i];



  for (int i=0;i<n;i++) {

    b[i] = a[i];

    b[n+i] = a[i];

  }



  vector<int> mins(n,inf);

  long long ans = INF;

  for (int i=0;i<n;i++) {

    long long kans = x*i;

    for (int j=0;j<n;j++) {

      mins[j] = min(mins[j],b[n+j-i]);

      kans += mins[j];

    }

    ans = min(ans,kans);

  }

  cout << ans << endl;

}
// Slower C++ solution:
#include <stdio.h>



int main() {

  int h[1501], w[1501];

  int n, m, i, j;

  

  while(scanf("%d%d", &n, &m) && (n|m)) {

    int dat[1500001] = {};

    n++, m++;

    h[0] = w[0] = 0;

    for(i=1; i<n; i++) { scanf("%d", &h[i]); h[i] += h[i-1]; }

    for(i=1; i<m; i++) { scanf("%d", &w[i]); w[i] += w[i-1]; }

    

    for(i=0; i<m-1; i++)

      for(j=i+1; j<m; j++)

	dat[w[j]-w[i]] ++;

    

    int cnt = 0;

    for(i=0; i<n-1; i++)

      for(j=i+1; j<n; j++)

	cnt += dat[h[j]-h[i]];

    

    printf("%d\n", cnt);

  }

  

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 13.656160602595202x):
#include <stdio.h>

#include <vector>



int main() {

  int h[1501], w[1501];

  int n, m, i, j;

  

  while(scanf("%d%d", &n, &m) && (n|m)) {

    std::vector<int> dat(std::max(n, m)*1500+1, 0);

    n++, m++;

    h[0] = w[0] = 0;

    for(i=1; i<n; i++) { scanf("%d", &h[i]); h[i] += h[i-1]; }

    for(i=1; i<m; i++) { scanf("%d", &w[i]); w[i] += w[i-1]; }

    

    for(i=0; i<m-1; i++)

      for(j=i+1; j<m; j++)

	dat[w[j]-w[i]] ++;

    

    int cnt = 0;

    for(i=0; i<n-1; i++)

      for(j=i+1; j<n; j++)

	cnt += dat[h[j]-h[i]];

    

    printf("%d\n", cnt);

  }

  

  return 0;

}
// Slower C++ solution:
#include<iostream>

#include<map>

#define rep(i,n) for(int i=0;i<n;i++)

#define foreach(i,c) for(__typeof(c.begin()) i=c.begin();i!=c.end();i++)

using namespace std;

void is(map<int,int> &mp,int n,int *a){

	for(int len=1;len<=n;len++)rep(i,n-len+1){

			int sum=0;

			rep(j,len)sum+=a[i+j];

			mp[sum]++;

		}

}

int main(){

	int m,n;

	while(cin>>n>>m,n){

		map<int,int> hm,wm;

		int h[1500],w[1500],ans=0;

		rep(i,n)cin>>h[i]; rep(i,m)cin>>w[i];

		is(hm,n,h); is(wm,m,w);

		foreach(i,hm)ans+=i->second*wm[i->first];

		cout<<ans<<endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.240154410299263x):
#include<cstdio>

#include<algorithm>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)



const int MX=1500*1000+1;

int n,m,H[1500],W[1500];

int h[MX],w[MX],sh,sw;



void comb(int *A,int *a,int k,int mx)

{

	fill_n(a,mx+1,0);

	rep(i,k)

	{

		int len=0;

		for(int j=i;j<k;j++)len+=A[j],a[len]++;

	}

}



int main()

{

	while(scanf("%d%d",&n,&m),n)

	{

		sh=sw=0;

		rep(i,n)scanf("%d",H+i),sh+=H[i]; comb(H,h,n,sh);

		rep(i,m)scanf("%d",W+i),sw+=W[i]; comb(W,w,m,sw);

		

		int ans=0;

		rep(i,min(sw,sh)+1)ans+=h[i]*w[i];

		printf("%d\n",ans);

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;



int w[1501]={0}, h[1501]={0};

int W[2250000]={0}, H[2250000]={0};



int sum(int* a , int i,int n,int size){

	int s = 0;

	for(int j=n ; j-- ; ){

		if( i >= size ){

			return 0;

		}

		s += a[i++];

	}

	return s;

}



int main(){

	int n,m,w_,h_;

	while( cin >> n >> m , n||m ){

		//int cnt_h[1001] = {0}

		int cnt_w[1000000] = {0};

		

		for(int i=0 ; i<n ; i++ ){

			cin >> h[i];

		}

		int i_=0;

		for(int j=1 ; j <= n ; j++ ){

			for(int i=0 ; i+j <= n ; i++ ){

				H[i_++] = sum( h , i , j , n );

			}

		}

		/*for(int i=0 ; i<i_ ; i++ ){

			cnt_h[ H[i] ]++;

		}*/

		

		for(int i=0 ; i<m ; i++ ){

			cin >> w[i];

		}

		int j_=0;

		for(int j=1 ; j <= m ; j++ ){

			for(int i=0 ; i+j <= m ; i++ ){

				W[j_++] = sum( w , i , j , m );

			}

		}

		for(int i=0 ; i<j_ ; i++ ){

			cnt_w[ W[i] ] += 1;

		}

		/*for(int i=0 ; i<j_ ; i++ ){

			cout << "W[" << i << "] : " << W[i] << endl;

		}*/

		

		int ans = 0;

		for(int i=0 ; i < i_ ; i++ ){

			//if( H[i] <= 1000 && H[i] >= 0 )

				ans += cnt_w[ H[i] ];

			//for(int j=0 ; j < j_ ; j++ ){

			//	if( W[j] == H[i] ) ans++;

			//}

		}

		//cout << "ans : " << ans << endl;

		cout << ans << endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 9.12014408380978x):
#include <iostream>

#include <cstdio>

#include <vector>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <algorithm>

#include <string>

using namespace std;



int N, M;

int H[1502], W[1502];



int sum_h(int i, int j){

	return (H[i] - H[j+1]);

}



int sum_w(int i, int j){

	return (W[i] - W[j+1]);

}



int main(){

	while( cin >> N >> M, N || M ){

		vector<int> h(N), w(M);

		for(int i=0; i < N ; i++ ) cin >> h[i];

		for(int i=0; i < M ; i++ ) cin >> w[i];

		

		// テァツエツッテァツゥツ催・ツ陳?

		fill(H, H + 1500, 0);

		fill(W, W + 1500, 0);

		for(int i=0 ; i < N ; i++ ) H[0] += h[i];

		for(int i=0 ; i < M ; i++ ) W[0] += w[i];

		for(int i=1 ; i < N ; i++ ) H[i] = H[i-1] - h[i-1];

		for(int i=1 ; i < M ; i++ ) W[i] = W[i-1] - w[i-1];

		

		for(int i=0 ; i < N ; i++ ){

			for(int j = i+1 ; j < N ; j++ ){

				h.push_back( sum_h(i, j) );

			}

		}

		for(int i=0 ; i < M ; i++ ){

			for(int j = i+1 ; j < M ; j++ ){

				w.push_back( sum_w(i, j) );

			}

		}

		

		map<int,int> memo;

		for(int i=0 ; i < h.size() ; i++ ){

			if( memo.count( h[i] ) ){

				memo[h[i]]++;

			}else{

				memo[h[i]] = 1;

			}

		}

		int ans = 0;

		for(int i=0 ; i < w.size() ; i++ ){

			if( memo.count( w[i] ) ){

				ans += memo[w[i]];

			}

		}

		cout << ans << endl;

	}

}