akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>

int main(){
    int n,x,t;
    scanf("%d %d %d", &n, &x, &t);
    int p = n / x;
    int q = n % x;
    int ans;
    if(q == 0) ans = p * t;
    else ans = (p+1) * t;
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 1724
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define ll long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define testcase ll T; cin >> T; for (ll tc = 1; tc <= T; tc++)
#define M 1000000007
#define MM 2000000000000000000
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
#define r2 1.41421356237
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //testcase {
 int n;
 cin>>n;
 cout<<!n;
  //}
  return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N,A; cin >> N >> A;

	if(N%500 > A) cout << "No" << endl;
	else cout << "Yes" << endl;

	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef set<int> si;
typedef map<string, int> msi;
typedef long long ll;
const ll INF = 1e18L + 1;

double p[3100];
double dp[3100][3100];
int main()
{
  int n;
  scanf("%d", &n);
  rep(i, n) scanf("%lf", p + i + 1); // p[i] <- ith coin
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++)
  {
    // dp[i][0] = dp[i - 1][0] * (1 - p[i]);
    for (int j = 0; j <= i; j++)
    {
      dp[i][j] += dp[i - 1][j - 1] * (p[i]);
      dp[i][j] += dp[i - 1][j] * (1 - p[i]);
      // dp[i][j+1] = dp[i-1][j]
    }
  }
  double ans = 0;
  for (int i = n / 2 + 1; i <= n; i++)
    ans += dp[n][i];
  printf("%.12f\n", ans);
  return 0;
}

Measured memory_bytes: 72320
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, T;
    cin >> n >> T;
    long long time = 0;
    long long pre = 0;
    for(int i = 0; i < n; ++i) {
        long long t;
        cin >> t;
        if(pre >= t) {
            time += T - (pre - t);
        } else {
            time += T;
        }
        pre = t + T;
    }
    cout << time << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>

struct Card {
    char suit;
    int value;
};

void trace(Card a[], int size) {
    for (int i = 0; i < size; ++i) {
        if (i > 0) {
            printf(" ");
        }
        printf("%c%d", a[i].suit, a[i].value);
    }
    printf("\n");
}

void BubbleSort(Card A[], int N) {
    int count  = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = N - 1; j > i; --j) {
            if ( A[j].value < A[j-1].value ){
                std::swap(A[j], A[j-1]);
                ++count;
            }
        }
    }

    trace(A, N);
}

void SelectionSort(Card A[], int N) {
    int count  = 0;
    for (int i = 0; i < N; ++i) {
        int min = i;
        for (int j = i; j < N; ++j) {
            if (A[j].value < A[min].value) {
                min = j;
            }
        }
        if (i != min) {
            std::swap(A[i], A[min]);
            count++;
        }
    }

    trace(A, N);
}

bool IsStable (Card A[], Card B[], int N) {
    for (int i = 0; i < N; ++i) {
        if (A[i].suit != B[i].suit || A[i].value != B[i].value) {
            return false;
        }
    }
    return true;
}

int main() {
    int N;
    Card A[100], B[100];

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i].suit >> A[i].value;
        B[i] = A[i];
    }

    BubbleSort(A, N);
    printf("Stable\n");
    SelectionSort(B, N);
    IsStable(A, B, N) ? printf("Stable\n") : printf("Not stable\n");
    return 0;
}

Measured memory_bytes: 3220
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String args[]) {
        try (Scanner in = new Scanner(System.in)) {

            int N = in.nextInt();
            int K = in.nextInt();

            long[] x = new long[N];
            long[] y = new long[N];
            for (int i = 0; i < N; i++) {
                x[i] = in.nextInt();
                y[i] = in.nextInt();
            }

            long[] x2 = Arrays.copyOf(x, N);
            Arrays.sort(x2);
            long[] y2 = Arrays.copyOf(y, N);
            Arrays.sort(y2);

            long area = Long.MAX_VALUE;
            for (int i = 0; i < N; i++) {
                for (int i2 = K - 1; i2 < N; i2++) {
                    for (int j = 0; j < N; j++) {
                        for (int j2 = K - 1; j2 < N; j2++) {

                            int count = 0;
                            for (int k = 0; k < N; k++) {
                                if (isInside(x2[i], y2[j], x2[i2], y2[j2], x[k], y[k])) {
                                    count++;
                                    if (count >= K) {
                                        break;
                                    }
                                }
                            }
                            if (count >= K) {
                                area = Math.min(area, Math.abs(x2[i] - x2[i2]) * Math.abs(y2[j] - y2[j2]));
                            }
                        }
                    }
                }
            }

            System.out.println(area);
        }
    }

    private static boolean isInside(long xi, long yi, long xj, long yj, long xk, long yk) {
        if (xk < Math.min(xi, xj) || xk > Math.max(xi, xj)) {
            return false;
        }
        if (yk < Math.min(yi, yj) || yk > Math.max(yi, yj)) {
            return false;
        }
        return true;
    }
}


Measured memory_bytes: 24660
import java.util.Scanner;

class Main{

	static char[][] map;
	static int N;
	static int M;
	static boolean flag;
	static int ans;



	public static void main(String[] args) {



		Scanner sc = new Scanner(System.in);			//文字の入力
		String string = sc.next();
		char[] cs = string.toCharArray();
		boolean[] flag =new boolean[3];
		for(int i = 0;i < 3;i++){
			if(cs[i] == 'a'){
				flag[0] = true;
			}else if(cs[i] == 'b'){
				flag[1] = true;
			}else if(cs[i] == 'c'){
				flag[2] = true;
			}
		}
		
		if(flag[0] && flag[1] && flag[2]){
			System.out.println("Yes");
		}else{
			System.out.println("No");

		}




	}


}

class Pair implements Comparable{
	String from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}





Measured memory_bytes: 21712
#include <bits/stdc++.h>
using namespace std;

string s;
int n,bf,r,l,cnt;

int main(){
  int i;
  while(1){
    cin >> n;
    if(n==0)break;
    cnt=0;
    bf=0;
    r=0;
    l=0;
    for(i=0;i<n;i++){
      cin >> s;
      if(s=="lu")l++;
      if(s=="ru")r++;
      if(s=="ld")l--;
      if(s=="rd")r--;
      if(l==r&&l!=bf){
	bf=l;
	cnt++;
      }
    }
    cout << cnt << endl;
  }
  return 0;
}



Measured memory_bytes: 3136
from collections import defaultdict
s = list(map(int,input().split()))
n=s[0]
k=s[1]
sunu={}
for i in range(1,n+1):
    sunu[i]=0
for i in range(k):
    s = list(map(int, input().split()))
    d=s[0]
    s = list(map(int, input().split()))
    for j in s:
        sunu[j]+=1
ans=0
for i in sunu:
    if sunu[i]==0:
        ans+=1
print(ans)

Measured memory_bytes: 9464
#include <bits/stdc++.h>
#include <iostream>
#include <string>
using namespace std;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)

//--------------------------------------------------------------------



int main() {
    int k, x;
    cin >> k >> x;
    string judge = "No";
    if (k*500 >= x) judge = "Yes";
    cout << judge << endl;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(void){
    int i,N;
    scanf("%d",&N);
    int a[N];
    for(i=0;i<N;i++){
        scanf("%d",&a[i]);
    }
    int val,sum = 0;
    for(i=0;i<N;i++){
        if(i==0){
            sum +=abs(a[i]);
        }
        else if(i == N-1){
            sum += abs(a[i]-a[i-1]) + abs(a[i]);
        }
        else{
            sum += abs(a[i]-a[i-1]);
        }
    }
    for(i=0;i<N;i++){
        if(i==0){
            val = sum - abs(a[i])-abs(a[i+1]-a[i])+abs(a[i+1]);
        }
        else if(i == N-1){
            val = sum -abs(a[i])-abs(a[i]-a[i-1])+abs(a[i-1]);
        }
        else{
            val = sum - abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]);
        }
        printf("%d\n",val);
    }
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int A, B, C;
  cin >> A >> B >> C;
  if (((A == B) && B != C) || ((B == C) && C != A) || ((A == C) && C != B)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main()
{
	int N = 0;

	cin >> N;

	vector<pair<int, int>> position;

	for (int i = 0; i < N; ++i) {
		pair<int, int> curPos;
		cin >> curPos.first >> curPos.second;
		position.push_back(curPos);
	}

	map<pair<int, int>, int> dist;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (i != j) {
				pair<int, int>curDist = make_pair(position[i].first - position[j].first, position[i].second - position[j].second);
				if (dist.count(curDist) == 0) {
					dist[curDist] = 1;
				}
				else {
					++dist[curDist];
				}
			}
		}
	}

	int maxDistCount = 0;
	for(const auto& curDist: dist){
		int curCount = curDist.second;
		if (curCount > maxDistCount) {
			maxDistCount = curCount;
		}
	}

	cout << N - maxDistCount << endl;

	return 0;
}

Measured memory_bytes: 384
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
  
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
  
using namespace std;
  
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
  
const int INF=1<<29;
const double EPS=1e-9;
  
const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};


int main() {
  int N, K;
  cin >> N >> K;
  vector<int> X(N);
  for(int i = 0; i < N; i++) {
    cin >> X[i];
  }
  int sum = 0;
  for(int i = 0; i < N; i++) {
    sum += 2 * min(abs(K - X[i]), abs(X[i]));
  }
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
#define pb push_back
#define IT iterator
#define SZ(a) ((int)a.size())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N=17,size=1<<20,mod=998244353,inf=2e9;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

//math
ll mult(ll a,ll b,ll p) {
	a=(a%p+p)%p; b=(b%p+p)%p;
	ll c=(ld)a*b/p;
	return a*b-c*p;
}
ll gcd(ll a,ll b) {return !a?b:gcd(b%a,a);}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
ll power(ll a,ll b=mod-2) {
	ll c=1;
	while(b) {
		if(b&1) c=c*a%mod;
		b /= 2; a=a*a%mod;
	}
	return c;
}
ll Power(ll a,ll b=mod-2) {
	ll c=1;
	while(b) {
		if(b&1) c=mult(c,a,mod);
		b /= 2; a=mult(a,a,mod);
	}
	return c;
}

ll n,x[N],y[N],p[N],w[1<<N],f[1<<N][N],lg[1<<N];

struct rec {
	ll x,y;
	bool operator <(rec b) const {
		return x<b.x;
	}
} a[N];

ll calc(int now) {
	ll tot,s,ans=1e18,tmp,mid;
	
	tot=s=0;
	for(int i=0;i<n;i++)
		if(now>>i&1) a[++tot]=(rec){x[i],p[i]},s+=p[i];
	sort(a+1,a+tot+1);
	mid=s+1>>1;
	for(int i=1;i<=tot;i++)
		if(mid<=a[i].y) {
			tmp=0;
			for(int j=1;j<=tot;j++) tmp+=a[j].y*abs(a[i].x-a[j].x);
			ans=min(ans,tmp); break;
		}
		else mid-=a[i].y;
	
	tot=s=0;
	for(int i=0;i<n;i++)
		if(now>>i&1) a[++tot]=(rec){y[i],p[i]},s+=p[i];
	sort(a+1,a+tot+1);
	mid=s+1>>1;
	for(int i=1;i<=tot;i++)
		if(mid<=a[i].y) {
			tmp=0;
			for(int j=1;j<=tot;j++) tmp+=a[j].y*abs(a[i].x-a[j].x);
			ans=min(ans,tmp); break;
		}
		else mid-=a[i].y;
	
	return ans;
}

int main() {
	qr(n);
	for(int i=0;i<=n;i++) lg[1<<i]=i;
	for(int i=0;i<n;i++)
		qr(x[i]),qr(y[i]),qr(p[i]);
	int s=(1<<n)-1;
	memset(f,63,sizeof f);
	f[0][0]=0;
	for(int i=1;i<=s;i++) {
		f[i][0]=f[i&(i-1)][0];
		int j=lg[i&-i];
		f[i][0] += min(abs(x[j]),abs(y[j]))*p[j];
	}
	pr2(f[s][0]);
	for(int i=1;i<(1<<n);i++) w[i]=calc(i);
	for(int t=1;t<=n;t++) {
 		for(int i=1;i<=s;i++)
			for(int j=i;	;j=(j-1)&i) {
				f[i][t]=min(f[i][t],f[j][t-1]+w[i^j]);
				if(!j) break;
			}
		pr2(f[s][t]);
	}
	return 0;
}


Measured memory_bytes: 21256
#include <cmath>
#include <iostream>
#include <vector>

// template <typename T>
// void swap(T& a, T& b) {
//     T t = a;
//     a = b;
//     b = t;
// }

bool is_prime(int n) {
    for (size_t i = 2, len = static_cast<int>(std::sqrt(n) + 1); i < len; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int n, m;
    std::cin >> n;
    int c = 0;
    while (std::cin >> m) {
        if (is_prime(m)) c++;
    }

    std::cout << c << std::endl;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
#define int long long
using namespace std;
void solve(){
    int n,h,w,ans;
    cin >> n >> h >> w;
    ans = (n - h + 1) * (n - w + 1);
    cout << ans << endl;
}
main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 256
<?php
fscanf(STDIN, "%d %d", $n, $k);
$p = explode(' ', trim(fgets(STDIN)));

sort($p, SORT_NUMERIC);
$total = 0;

for ($i = 0; $i < $k; $i++) {
    $total += $p[$i];
}

echo "{$total}\n";


Measured memory_bytes: 16368
#include <bits/stdc++.h>
using namespace std;
#define sd(x) scanf("%d", &x)
#define sz(v) (int) v.size()
#define pr(v) For(i, 0, sz(v)) {cout<<v[i]<<" ";} cout<<endl;
#define slld(x) scanf("%lld", &x)
#define all(x) x.begin(), x.end()
#define For(i, st, en) for(ll i=st; i<en; i++)
#define tr(x) for(auto it=x.begin(); it!=x.end(); it++)
#define fast std::ios::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define ll long long
#define int long long
#define ld long double
#define mp make_pair
#define F first
#define S second
typedef pair<int, int> pii;
typedef vector<int> vi;
#define pi 3.141592653589793238
#define MOD 1000000007
#define INF 1000000000000000007LL


const int N = 100005;
 
// it's swapnil07 ;)
 
#ifdef SWAPNIL07
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";
#else
#define endl '\n'
#define trace(...)
#define end_routine()
#endif


void solve(){
    int x, y, z; cin>>x>>y>>z;
    x -= z;
    cout<<(x/(y+z));
}


signed main()
{
    fast
    #ifdef SWAPNIL07
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int t=1; 
    // cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    int a, b, k;
    cin >> a >> b >> k;

    for (int i = min(a, b); i >= 1; i--){
        if (a % i == 0 && b % i == 0){
            k--;
            if(k == 0) cout << i << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, s, n) for (int i = (s); i < (n); i++)
#ifdef LOCAL
#define INPUT_FILE                   \
  ifstream in("abc171/abc171_b.txt"); \
  cin.rdbuf(in.rdbuf());
#define print_vec(v) \
rep(l, v.size()) { cout << v[l] << " "; } \
cout << endl;
#else
#define INPUT_FILE
#define print_vec(v)
#endif
#define CIN_OPTIMIZE \
  cin.tie(0);        \
  ios::sync_with_stdio(false);
typedef pair<int, int> P;
typedef long long ll;
typedef pair<ll, ll> pl;
const int INF = 100100100;
const ll LINF = 1e18+100;
const int MOD = 1e9 + 7;

int main() {
  INPUT_FILE CIN_OPTIMIZE;

  int N, K;
  cin >> N >> K;
  
  vector<int> c(N);
  rep(i, N) { cin >> c[i]; }
  sort(c.begin(), c.end());

  ll ans = 0;
  rep(i, K) { ans += c[i]; }

  cout << ans << endl;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;

struct s_t{
  ll a,b;
};

bool asc(s_t left,s_t right) {
  return left.a == right.a ? left.b > right.b : left.a < right.a;
}

int main (){
  ll n,m;
  cin>>n>>m;
  s_t k;
  vector<s_t>v(n,k);
  for(ll i=0;i<n;i++){
    cin>>k.a>>k.b;
    v[i]=k;
  }
  ll ans=0;
  sort(v.begin(),v.end(),asc);
  for(ll i=0;i<n;i++){
    if(v[i].b<=m){
      m-=v[i].b;
      ans+=v[i].a*v[i].b;
    }
    else{
      ans+=v[i].a*m;
      m=0;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <random>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
long DP[100001][13];
void Calc(){
	string S = res();
	DP[0][0] = 1;
	for(int i=0;i<S.length();i++){
		for(int j=0;j<13;j++){
			DP[i][j] %= mod;
			if(S[i] == '?'){
				for(int k=0;k<10;k++){
					DP[i+1][(j*10+k)%13] += DP[i][j];
				}
			}
			else{
				DP[i+1][(j*10+S[i]-'0')%13] += DP[i][j];
			}
		}
	}
	cout << DP[S.length()][5]%mod << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 10704
#include<bits/stdc++.h>
using namespace std;
long long DP[2020][2020];
pair<long long,int> C[2020];
int main()
{
	int N;
	cin>>N;
	for(int i=0;i<N;i++)
	{
		cin>>C[i].first;
		C[i].second=i;
	}
	sort(C,C+N);
	reverse(C,C+N);
	for(int i=0;i<N;i++)
		for(int j=0;j<=i;j++)
		{
			int k=i-j;
			DP[j+1][k]=max(DP[j+1][k],DP[j][k]+C[i].first*(C[i].second-j));
			DP[j][k+1]=max(DP[j][k+1],DP[j][k]+C[i].first*(N-C[i].second-1-k));
		}
	long long Ans=0;
	for(int i=0;i<=N;i++)
		Ans=max(Ans,DP[i][N-i]);
	cout<<Ans<<endl;
	return 0;
}


Measured memory_bytes: 26300
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int calc(int d,int w,int h){
	double a[3];
	double d1=(d/2);
	double w1=(w/2);
	double h1=(h/2);
	double tmp;


	a[0]=sqrt((d1*d1)+(w1*w1));
	a[1]=sqrt((d1*d1)+(h1*h1));
	a[2]=sqrt((w1*w1)+(h1*h1));

	for(int i=0;i<2;i++){
		for(int j=2;j>i;j--){
			if(a[j-1]>a[j]){
				tmp=a[j-1];
				a[j-1]=a[j];
				a[j]=tmp;
			}
		}
	}

	return a[0];

}

int main(){
	int d,w,h;
	int n;
	int min,a;

	while(scanf("%d %d %d",&d,&w,&h)){
		if(d==0 && w==0 && h==0){break;}
		scanf("%d",&n);
		for(int i=0;i<n;i++){
			scanf("%d",&a);
			if(a>calc(d,w,h)){
				printf("OK\n");
			}else{
				printf("NA\n");
			}
		}
	}
	
	calc(d,w,h);

	return 0;
}


Measured memory_bytes: 1972
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<double> data(n);
    for (int i = 0; i < n; i++){
        cin >> data.at(i);
    }

    sort(data.begin(), data.end());

    double first = 0;
    first = (data.at(0) + data.at(1)) / 2.0;
    for (int i = 2; i < n; i++){
        first = (first + data.at(i)) / 2.0;
    }

    cout << first << endl;
}


Measured memory_bytes: 256
//itp1_9-b
#include <iostream>
#include <string>
#include <cctype>
using namespace std;

int main(){
 string s,s1,s2;
 int m,h;

 while(true){
  cin>>s;
  if(s=="-") break;
  cin>>m;
  for(int i=0;i<m;i++){
   cin>>h;
   s1=s.substr(0,h);
   s2=s.substr(h);
   s=s2+s1;
  }
  cout<<s<<endl;
 }
return 0;
}

Measured memory_bytes: 1216
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
	long long n, t = 0;
	cin >> n;
	n += 1;
	while (n--) {
		if (n % 3 != 0 && n % 5 != 0)t += n;
	}
	cout << t << endl;
	return 0;
}

Measured memory_bytes: 3628
S = input()
INF = 10**9+7
dp = [0,0,0]
N = 1
for i in range(len(S)):
  if S[i]=='A':
    dp[0] += N
    dp[0] %= INF
  elif S[i]=='B':
    dp[1] += dp[0]
    dp[1] %= INF
  elif S[i]=='C':
    dp[2] += dp[1]
    dp[2] %= INF
  else:
    a = dp[0]
    b = dp[1]
    dp[0] = N + dp[0]*3
    dp[1] = a + dp[1]*3
    dp[2] = b + dp[2]*3
    dp[0] %= INF
    dp[1] %= INF
    dp[2] %= INF
    N = (3*N)%INF
print(dp[2]%INF)


Measured memory_bytes: 3188
import sys
MOD = 10**9+7
def main():
    input = sys.stdin.readline
    N,K=map(int, input().split())
    ans=Mint()
    cnt=[Mint() for _ in range(K+1)]
    for g in range(K,0,-1):
        cnt[g]+=pow(K//g,N,MOD)
        for h in range(g+g,K+1,g):
            cnt[g]-=cnt[h]
        ans+=g*cnt[g]
    print(ans)

class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other)) % MOD
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Measured memory_bytes: 82116
import sys
from string import ascii_lowercase as a2z

input = sys.stdin.readline


def main():
    N = int(input())

    i = 1
    min_v = 1
    max_v = 26
    while True:
        if N <= max_v:
            j = N - min_v
            ans = ""
            for _ in range(i):
                r = j % 26
                ans = "".join([a2z[r], ans])
                j = (j - r) // 26
            break
        min_v += 26 ** i
        i += 1
        max_v += 26 ** i

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9980
#include <bits/stdc++.h>
#include <math.h>

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int s, w;
    cin >> s >> w;
    if (s <= w)
        cout << "unsafe" << endl;
    else {
        cout << "safe" << endl;
    }
}

Measured memory_bytes: 3600
import itertools
import math
n = int(input())
x_y = [list(map(int, input().split())) for _ in range(n)]
ans = 0
perm = itertools.permutations(range(n))
for p in perm:
    for i in range(n - 1):
        pos = p[i]
        next_pos = p[i + 1]
        ans += ((x_y[pos][0] - x_y[next_pos][0]) ** 2 + (x_y[pos][1] - x_y[next_pos][1]) ** 2) ** (1/2)
print(ans / math.factorial(n))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e4+20;
int pri[N],vis[N],pn=0;
int fac[N];//µÚi¸öËØÊýµÄÃÝ´Î 
//¸ø³ön<=1e3,Çón!Ô¼Êý¸öÊýmod1e9+7
//·Ö½ân!ÎªËØÒò×ÓÐÎÊ½ ÔòÕû³ýn!¸öÊýÎª ¸÷¸öÃÝ³Ë»ý 
void init()
{
	memset(vis,-1,sizeof(vis));
	for(int i=2;i<N;i++)
	{
		if(vis[i]==-1)
		{
			pri[++pn]=i;
			for(int j=i+i;j<N;j+=i)
			{
				vis[j]=1;
			}
		}
	}
}
void factor(int x)
{
	for(int i=1;i<=pn;i++)
	{
		while(x%pri[i]==0)
		{
			fac[i]++;
			x/=pri[i];
		}
		if(x==1)
		return;
	}
	
}

int main()
{
 	ll n;
 	init();
	while(cin>>n)
	{
		memset(fac,0,sizeof(fac));
		if(n==1)
		{
			puts("1");
			continue;
		}
		for(int i=2;i<=n;i++)
		{
			factor(i);
		}
		ll ans=1;
		for(int i=1;i<=pn;i++)
		{
			if(fac[i]==0)
			continue;
			ans=(ans*(fac[i]+1))%mod;
		}
		cout<<ans<<endl;
	} 
 
	return 0;
}


Measured memory_bytes: 384
#include <vector>
#include <list>
#include <map>
#include <set>
#include "queue"
#include <deque>
#include <stack>
#include <numeric>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <complex>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include "fstream"
using namespace std;
#define PI acos(-1)
#define MOD 1000000007
#define pii pair<long long ,long long >
#define ll  long long int
#define loop(i,n) for(ll i=0;i<n;i++)
#define loop2(i,n) for(ll i = 1;i<=n;i+=1)
#define pb push_back
#define EPS 1e-8
inline ll gcd(ll a, ll b){ ll t; while (b){ a = a%b; t = a; a = b; b = t; }return a; }
using namespace std;

ll ans = 1;



bool isprime(ll n)
{
    for(ll j = 2;j<=sqrt(n);j+=1)
    {
        if(n%j==0&&n!=j)
            return false;
    }
    return true;
}


ll cool(ll x,ll y)
{
    ll ans  =0  ;
    ll res = y;
    while(x>=res)
    {
        
        ans+=x/res;
        res*=y;
    }
    return ans;
}



int main()
{
//    freopen("/Users/ashish/Desktop/manic_moving.txt", "r", stdin);
//    freopen("/Users/ashish/Desktop/A-large-practice.out.txt", "w", stdout);
    //cout<<cool(8, 2);
    ll n;
    cin>>n;
    ll ans1 = 1;
    for(ll j = 2;j<=n;j+=1)
    {
        if(isprime(j))
        {
            //cout<<j<<"-> ";
            ll z = cool(n, j);
            //cout<<z<<endl;
            z+=1;
            ans1*=z;
            ans1%=MOD;
        }
    }
    cout<<ans1;
    
    
    return 0;
}


Measured memory_bytes: 256
#include<vector>
#include<iostream>
using namespace std;
#define MAX_V 1000
#define MAX_E 2000
#define INF 1e9
struct edge {
	int from, to, cost;
};
int V, E;
int d[MAX_V];
edge es[MAX_E];
bool find_negative_loop(int s)
{
	for (int i = 0; i < MAX_V; i++)
	{
		d[i] = INF;
	}
	d[s] = 0;
	int count = 0;
	//bool update = false;
	while (true)
	{
		bool update = false;
		count++;
		for (int i = 0; i < E; i++)
		{
			if ((d[es[i].from] != INF) &&( d[es[i].to] > d[es[i].from] + es[i].cost))
			{
				if (count == V)
				{
					return true;
				}
				d[es[i].to] = d[es[i].from] + es[i].cost;
				update = true;
			}
		}
		if (!update)
		{
			break;
		}
	}
	return false;

}


int main()
{
	int r;
	cin >> V >> E >> r;
	for (int i = 0; i < E; i++)
	{
		cin >> es[i].from >> es[i].to >> es[i].cost;
	}
	if (find_negative_loop(r))
	{
		cout << "NEGATIVE CYCLE" << endl;
	}
	else
	{
		for (int i = 0; i < V; i++)
		{
			if (d[i] == INF)
			{
				cout << "INF" << endl;
			}
			else
			{
				cout << d[i] << endl;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 3116
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = float("inf")
 
 
def find_lt(a, x):
    i = bisect_left(a, x)
    if i:
        return i
    return 0
 
 
def find_gt(a, x):
    i = bisect_right(a, x)
    if i != len(a):
        return i
    return len(a)
 
 
def main():
    N = int(input())
    A = list(sorted(list(map(int, input().split()))))
    B = list(sorted(list(map(int, input().split()))))
    C = list(sorted(list(map(int, input().split()))))
 
    ans = 0
    for b in B:
        a = find_lt(A, b)
        b = N - find_gt(C, b)
        ans += a * b
    print(ans)
 
 
if __name__ == '__main__':
    main()

Measured memory_bytes: 23732
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		if((s.contains("E")&&!s.contains("W"))||(s.contains("W")&&!s.contains("E"))) {
			System.out.println("No");
			return;
		}
		if((s.contains("N")&&!s.contains("S"))||(s.contains("S")&&!s.contains("N"))) {
			System.out.println("No");
			return;
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

//-------------------------------------------------

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,y; cin>>n>>y;
    int a1=-1,a2=-1,a3=-1;
    rep(i,n+1)rep(j,n-i+1){
        int sum=10000*i+5000*j+1000*(n-i-j);
        if (sum==y){
            a1=i, a2=j, a3=n-i-j;
            break;
        }
    }
    cout<<a1<<" "<<a2<<" "<<a3<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long L[100];
	long long N;
	cin>>N;
	L[0]=2;
	L[1]=1;
	for(long long i=2;i<100;i++){
		L[i]=L[i-1]+L[i-2];
	}
	cout<<L[N]<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
const ll mod = 1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = a; i >= (b); --i)
#define all(x) x.begin(), x.end()
#define pb  push_back
#define mb  make_pair
#define itn int
#define fi first
#define se second

void solve()
{
    ll a, b, c, d;
    cin >> a >> b  >> c >> d;
    while(1)
    {
        c -= b;
        if(c <= 0)
        {
            cout <<"Yes";
            return;
        }
        a -= d;
        if(a <= 0)
        {
            cout << "No";
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

	solve();
	return 0;
}


Measured memory_bytes: 3652
n=int(input())
def a(a):
    return a//100000 + (a//10000)%10+(a//1000)%10 + (a//100)%10 + (a//10)%10 + a%10
b=[]

if n == 100000:
    print(10)
else:    
    for i in range(1,n//2 +1):
        b.append(a(i)+a(n-i))
    print(min(b))

Measured memory_bytes: 3480
#include <iostream>

using namespace std;

int main()
{
    long a, b, c, d, e;

    cin >> a >> b >> c;

    if ((a - c) >= 0) {
      d = (a - c);
      e = b;
    } else if ((a + b - c) >= 0) {
      d = 0;
      e = (a + b - c);
    } else {
      d = 0;
      e = 0;
    }

    cout << d << " " << e << endl;

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

using E = System.Linq.Enumerable;

public class Program
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());

        var sum = 0L;
        for (int i = 0; i < n; ++i)
        {
            if ((i + 1) % 3 == 0 || (i + 1) % 5 == 0)
            {
                continue;
            }

            sum += i + 1;
        }

        Console.WriteLine(sum);
    }
}


Measured memory_bytes: 27476
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <list>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()

int isp[1100];
const int MOD = 1e9 + 7;

void solve(){
	int n; scanf("%d", &n);
	for(int i=2;i<=n;i++)isp[i] = 1;
	ll ans = 1;
	for(int i=2;i<=n;i++){
		if(isp[i]){
			int cnt = 0;
			for(int j=i;j<=n;j+=i){
				isp[j] = 0;
				int t = j;
				while(t % i == 0)++cnt, t /= i;
			}
			ans = ans * (cnt+1) % MOD;
		}
	}
	printf("%lld", ans);
}

int main(){
	int Tc = 1;// scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
from itertools import product,permutations

n,m,R = map(int,input().split())
r = list(map(int,input().split()))
INF = 10**10
d = [[INF for i in range(n)] for j in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

for k,i,j in product(range(n),range(n),range(n)):d[i][j] = min(d[i][j],d[i][k]+d[k][j])

ans = INF

for v in permutations(r,R):
    dis = 0
    for i in range(R-1):
        dis += d[v[i]-1][v[i+1]-1]
    ans = min(ans,dis)

print(ans)


Measured memory_bytes: 48728
from itertools import accumulate
import bisect
n,m,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
a_acc = [0] + list(accumulate(a))
b_acc = list(accumulate(b))
#print(a_acc)
#print(b_acc)

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        break

    bn = bisect.bisect_right(b_acc, rem)
    #print(bn)
    ans = max(ans, an + bn)

print(ans)

Measured memory_bytes: 133460
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long int
#define int ll
//#define slld(t) scanf("%lld",&t)
// #define sd(t) scanf("%d",&t)
// #define pd(t) printf("%d\n",t)
//#define plld(t) printf("%lld\n",t)
#define vec vector < int >
#define vecp vector < pair < int , int > >
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define debug(x)   cerr<<#x<<": "<<x<<endl
#define pii pair < int , int >
#define pll pair < ll , ll > 
#define pdd pair<double , double>
#define debug(x)   cerr<<#x<<": "<<x<<endl
#define mod  1000000007
#define N    200005
#define mod1 1000000007
#define mod2 998244353
#define bitcnt __builtin_popcountll
#define PI acos(-1)
#define s3   1.73205080757          // square root 3
const  int inf = (int)1e18+10 ;
const int MAX= 100;

 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ordered_set S;

int powmod(int x , int y){
	int res = 1;
	while(y > 0){
		if(y%2==1)
			res = (res*x)%mod;
		x = (x*x)%mod;
		y/=2;
	}
	return res;
}
int mul(int x , int y){
	return (x*y)%mod;
}

signed main(){
  fast;
 
  int x , y;
  cin >> x >> y;
  cout << (x*y)/__gcd(x , y) << endl;
 }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
	#define D(a) cerr << #a << " = " << a << endl
#else
	#define D(a)
	#define cerr false && cerr
#endif
#define fastio ios_base::sync_with_stdio(0); cin.tie(0)
#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) dforsn(i,0,n)
#define forn(i,n) forsn(i,0,n)
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first
#define endl '\n'
using pii = pair<int,int>;
using vi = vector<int>;
using ll = long long;

int main() {
	fastio;
	
    string s; cin >> s;
    int n = si(s), a = 0, b = 0;
    forn(i,n) if((s[i]=='0' && i&1) || (s[i]=='1' && !(i&1))) a++;  
    forn(i,n) if((s[i]=='1' && i&1) || (s[i]=='0' && !(i&1))) b++;  
    cout << min(a,b) << endl;
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
ll n;
int main(){
    char s;
    cin>>s;
    printf("%c\n",s+1);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INFLL LLONG_MAX/16 // 9223372036854775807
#define EPS 1e-9
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
#define Init() std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout<<fixed<<setprecision(15);
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    Init();
    ll n, m; cin >> n >> m;
    vector<pair<ll, ll>> key;
    rep(i, m){
        ll a, b, s = 0; cin >> a >> b;
        rep(j, b){
            ll c; cin >> c; c--;
            s |= (1ll<<c);
        }
        key.emplace_back(s, a);
    }

    // bitDP
    vector<ll> dp(1ll<<n, INFLL); dp[0] = 0;
    rep(s, 1ll<<n){
        rep(i, m){
            ll t = s | key[i].first;
            ll cost = dp[s] + key[i].second;
            chmin(dp[t], cost);
        }
    }
    ll ans = dp.back();
    if(ans == INFLL) ans = -1;
    cout << ans << endl;
}

Measured memory_bytes: 3696
#pragma once
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <utility>
#include <set>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <numeric>
#include <iomanip>
#define M_PI acos(-1)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1000000007;
const int MAX_V = 201;
int now = 0;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
struct edge {
	int t;
	edge(int _t) : t(_t) {}
};
bool use[100010];


vector<edge> te[100010];
vector<edge> fe[100010];
int d[100100];
ll rec(int num) {
	if (num == 0) return 0;
	return rec(num - 1) + num;
}
ll gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

ll calc(ll b,ll n){
	if (n < b) return n;
	return calc(b, n / b) + n % b;
}

void Solve() {

	int n, m;
	cin >> n >> m;
	ll nsum = 0;
	ll bef;
	for (size_t i = 0; i < n; i++)
	{
		
		ll x;
		cin >> x;
		if (i == 0) {
			bef = x;
			continue;
		}
		ll add = ((n - 1) - (i - 1)) * i;
		add %= INF; 
		add *= x - bef;
		add %= INF;
		nsum += add;
		nsum %= INF;
		bef = x;
	}
	ll msum = 0;
	for (size_t i = 0; i < m; i++)
	{
		ll x;
		cin >> x;
		if (i == 0) {
			bef = x;
			continue;
		}
		ll add = ((m - 1) - (i - 1)) * (i);
		add %= INF;
		add *= x - bef;
		add %= INF;
		msum += add;
		msum %= INF;
		bef = x;
	}
	ll res = nsum * msum;
	res %= INF;
	cout << res << endl;
}


int main() {
	Solve();
	return 0;
}



Measured memory_bytes: 6016
#include<stdio.h>
#include<stdbool.h>

int main(){
	int h,w,i,j;
	while(scanf("%d %d",&h,&w),h!=0 && w!=0){
			bool flags=true,flagl=false;
		for(i=0;i<h;i++){
			if(flagl) flagl=false;
			else flagl=true;
			flags=flagl;
			for(j=0;j<w;j++){
				if(flags){
					printf("#");
					flags=false;
				}
				else{
					printf(".");
					flags=true;
				}
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2000
top_three = [0, 0, 0]
for i in range(10):
    input_height = int(input())
    if top_three[0] < input_height:
        top_three[2] = top_three[1]
        top_three[1] = top_three[0]
        top_three[0] = input_height
    elif top_three[1] < input_height:
        top_three[2] = top_three[1]
        top_three[1] = input_height
    elif top_three[2] < input_height:
        top_three[2] = input_height

print(top_three[0])
print(top_three[1])
print(top_three[2])


Measured memory_bytes: 5600
#include <stdio.h>

int main(void){
	int H,W;	//白いマス目
	int h,w;	//塗りつぶす行、列
	scanf("%d %d",&H,&W);
	scanf("%d %d",&h,&w);
	
	int remain=(H*W)-(h*W)-(H-h)*w;
	printf("%d",remain);	//出力
	return 0;
}

Measured memory_bytes: 128
N,K=map(int,input().split())
import bisect
A=list(map(int,input().split()))
ruiseki=[0]*(N+1)
ruiseki[1]=A[0]
for i in range(1,N):
    ruiseki[i+1]=ruiseki[i]+A[i]
from collections import defaultdict
S=[]
for i in range(N):
    S+=[ruiseki[j+1]-ruiseki[i] for j in range(i,N)]
S.sort()
ans=0
for k in range(40,-1,-1):
    idx=bisect.bisect_left(S,pow(2,k))
    if len(S)-idx>=K:
        ans+=pow(2,k)
        S=[s-pow(2,k) for s in S[idx:]]
    else:
        S=[s%pow(2,k) for s in S]
        S.sort()
print(ans)

Measured memory_bytes: 30160
n, C = map(int, input().split())
time = 0
stc = []
for i in range(n):
    temp = list(map(int, input().split()))
    time = max(time, temp[1])
    stc.append(temp)
tv = [[0 for i in range(C)] for i in range(time + 1)]
for i in stc:
    s, t, c = i[0], i[1], i[2]
    for j in range(s, t + 1):
        tv[j][c - 1] = 1
ans = 0
for i in tv:
    ans = max(ans, sum(i))
print(ans)

Measured memory_bytes: 62780
N, X = map(int, input().split())
x = list(map(lambda x:abs(int(x)-X), input().split()))

#for i in range(N):
#	x[i] = abs(x[i] - X)

x.sort()
#x.reverse()

xmin = x[0]
#xmin = x[N-1]
'''
div = []
for i in range(int(xmin/2)+1, 0, -1):
	if xmin % i == 0:
		div.append(i)

for d in div:
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)
'''
for d in range(xmin,0,-1):
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)

Measured memory_bytes: 62704
import java.io.*;
import java.util.*;

public class Main{
  public static void main(String[] args)throws IOException{
   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
   String str = br.readLine();
                    str =br.readLine();

                    ArrayList<String> cards = new ArrayList<String>();
                    
                    while(str != null){
                    cards.add(str);
                    str = br.readLine();
                    }    

                    ArrayList<String> empty = new ArrayList<String>();

                    for(int i=1;i<=13;i++){
                        String s = "S " +i;
                                                
                        if(cards.indexOf(s) == -1){
                            empty.add(s);
                        }
                            
                    }

                    for(int i=1;i<=13;i++){
                       
                        String h = "H " +i;
                       
                        if(cards.indexOf(h) == -1){
                            empty.add(h);
                        }
                    }

                    for(int i=1;i<=13;i++){

                        String c = "C " +i;

                        if(cards.indexOf(c) == -1){
                            empty.add(c);
                        }
                    }

                        for(int i=1;i<=13;i++){
         
                            String d = "D " +i;
                            
                            if(cards.indexOf(d) == -1){
                                empty.add(d);
                            }                        
                        }     
                    
                    for(int i=0;i<empty.size();i++){
                        System.out.println(empty.get(i));
                    }
}
}

Measured memory_bytes: 24356
A, B, C, D = map(int, input().split())

def baisuu(a, b, n):
    return (b // n) - ((a-1) // n)

def gcd(d,c):
    if d > c:
        c, d = d, c
    
    x = c * d

    r = c % d
    while r != 0:
        c = d
        d = r
        r = c % d
    return x // d

def answer(a,b,c,d):
    cn = baisuu(a,b,c)
    dn = baisuu(a,b,d)
    cdn = baisuu(a,b,gcd(c,d))
    return (b-a+1) - (cn+dn-cdn)

print(answer(A,B,C,D))


Measured memory_bytes: 3064
#include <iostream>

using namespace std;

#define BIGGER(a, b)    ((a)>(b) ? (a--) : (b--))

int main(void)
{
  int A=0;
  int B=0;
  int coin = 0;
  
  cin >> A;
  cin >> B;
  
  coin += BIGGER(A,B);
  coin += BIGGER(A,B);

  cout << coin;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxx=1e5+2;
typedef long long ll;
int main(){
    int x; cin>>x;
    int ans=0;
    for(int i=1;i<=x;i++){
        int x=i;
        int cnt=0;
        while(x){
            cnt++; x/=10;
        }
        if(cnt&1) ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;

int main(){ 
string N;
  cin >> N;
  if(N[0]==N[2]){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256