akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = (int) 2e5 + 1;

string s, cur, r;
int n, ans = 1, nx;
int main(){
    cin >> s;
    n = (int)s.size();
    cur += s[0];
    for(int i = 1; i < n; i++){
        r += s[i];
        if(cur == r){
            continue;
        }
        else {
            ans++;
            cur = r;
            r = "";
        }
    }
    cout << ans;
}


Measured memory_bytes: 640
let n, x, t =
    stdin.ReadLine().Split()
    |> Array.map int
    |> fun ary -> ary.[0], ary.[1], ary.[2]

let times =
    match n % x with
    | 0 -> n / x
    | int -> n / x + 1

printfn "%d" (times * t)


Measured memory_bytes: 29936
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int ar[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin>>n;
  cout<<ar[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define INF 1e9L
#define EPS 1e-9
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<int>())S
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define pb push_back
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
    string s;
    cin >> s;
    int ans = 0;
    int tmp = 0;
    REP(i, s.size()){
        if(s[i]=='A'||s[i]=='C'||s[i]=='G'||s[i]=='T')tmp++;
        else{
            ans = max(ans, tmp);
            tmp = 0;
        }
    }
    ans = max(ans, tmp);
    pr(ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define mp(a,b) make_pair(a,b)
#define vi vector<int>
#define mii map<int,int>
#define mpi map<pair<int,int>,int>
#define vp vector<pair<int,int> >
#define pb(a) push_back(a)
#define fr(i,n) for(i=0;i<n;i++)
#define rep(i,a,n) for(i=a;i<n;i++)
#define F first
#define S second
#define endl "\n"
#define fast std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define dom 998244353
#define pi 3.14159265
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define pii pair<int,int> 
#define mini 2000000000000000000
#define time_taken 1.0 * clock() / CLOCKS_PER_SEC
//mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
void shikhar7s(int cas)
{
    int n,i;
    cin>>n;
    int a[n+1],c=1,f=1;
    vi v;
    v.pb(1);
    fr(i,n+1)
    {
        cin>>a[i];
        if(a[i]>c)
            f=0;
        c-=a[i];
        if(c<10000000000000000)
            c*=2;
        if(i!=n)
        v.pb(c);
    }
    if(!f)
    {
        cout<<-1;
        return;
    }
    c=0;
    int ans=0;
    for(i=n;i>=0;i--)
    {
        c+=a[i];
        ans+=min(c,v[i]);
    }
    cout<<ans;
}
signed main()
{
    fast;
    int t=1;
    //cin>>t;
    int cas=1;
    while(cas<=t)
    {
    shikhar7s(cas);
    cas++;
    }
    return 0;
}

Measured memory_bytes: 5036
from collections import deque

h, w = map(int,input().split())

cnt = 0
maze = []
for i in range(h):
    t = list(input())
    cnt += t.count('.')
    maze.append(t)
    
dx = [0,0,1,-1]
dy = [1,-1,0,0]

queue = deque([(0, 0)])

distance = [[-1]*w for _ in range(h)]
distance[0][0] = 0

while queue:
    y, x = queue.popleft()
    for dxi, dyi in zip(dx, dy):
        if (0<=x+dxi<w and 0<=y+dyi<h) and maze[y+dyi][x+dxi] == "." and distance[y+dyi][x+dxi] == -1:
            distance[y+dyi][x+dxi] = distance[y][x]+1
            queue.append((y+dyi, x+dxi))

if distance[h-1][w-1] != -1:
    print(cnt-(distance[h-1][w-1]+1))
else:
    print(-1)

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

double x[8],y[8];
int root[8];
bool used[8];
double sum = 0;
int co = 0;

void calc(int N){
    int j1 =0 ;
    int j2 =0;
    for(int i = 0; i < N-1; i++){
        j1 = root[i]-1;
        j2 = root[i+1]-1;
        sum +=  sqrt(pow(x[j1]-x[j2],2)+pow(y[j1]-y[j2],2));
    }
    co++;
    return ;
}

void search(int n ,int N){
    if( n == N ){
        calc(N);
        return ;
    }
    for(int i = 1; i <= N; i++) if(!used[i]){
        root[n] = i;
        used[i] = true;
        search(n+1,N);
        used[i] = false;
    }
    return ;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++){
        cin >> x[i] >> y[i];
        used[i] = false;
    }
    used[N] = 0;
    search(0,N);
    cout << fixed << setprecision(12) << sum / co << endl;
 }



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
const ll INF=100000000000000001;
const double PI=3.141592653589;


int main(){
  int a,b; cin>>a>>b;
  int ans;
  if(a>=13)
  ans=b;
  else if(a>=6)
  ans=b/2;
  else
  ans=0;
  
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
void input()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}
using namespace std;
typedef long long ll ;
const long long N = 1e5,OO=0x3f3f3f3f;
ll n,weight,w[105],v[105];
ll dp[105][N+5];

int main()
{
    cin>>n>>weight;
    for(int i=0; i<n; i++)
        cin>>w[i]>>v[i];

    for(int i=0; i<105; i++)
        for(int j=0; j<=N; j++)
            dp[i][j]=1e18;

    for(int i=0; i<n; i++)
        dp[i][v[i]]=w[i];

    for(int i=1; i<n; i++)
    {
        for(int j=0; j<=N; j++)
        {
            ll &ret=dp[i][j];
            ret=min(ret,dp[i-1][j]);
            if(v[i]<=j)
                ret=min(ret,w[i]+dp[i-1][j-v[i]]);
            }
    }
    for(int i=N; i>=0; i--)
        if(dp[n-1][i]<=weight)
        {
            cout<<i<<endl;
            break;
        }
}


Measured memory_bytes: 85672
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int N,K;
    int sum=0;
    cin>>N>>K;
    for(int i=0;i<N;i++)
    {
        int x;
        cin>>x;
        if(x>=K) sum++;
    }
    cout<<sum;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define forn(i, n) for(int i=0; i<(int)(n); i++)
#define forne(i, a, b) for(int i=a; i<=(int)(b); i++)

#define gottagofast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl "\n"
using namespace std;

#define MAX (1002)
#define MOD (ll)(1e9 + 7)

char mat[MAX][MAX];
ll tabela[MAX][MAX];
int h, w;

ll dp(int r, int c) {
  if(r == h-1 and c == w-1) {
    return tabela[r][c] = 1;
  }
  if(tabela[r][c] != -1)
    return tabela[r][c];

  int res = 0;
  if(r+1 < h and mat[r+1][c] == '.') {
    res = (res + dp(r+1, c))%MOD;
  }
  if(c+1 < w and mat[r][c+1] == '.') {
    res = (res + dp(r, c+1))%MOD;
  }

  return tabela[r][c] = res;
}

int main() {
  cin >> h >> w;

  memset(tabela, -1, sizeof(tabela));

  for(int row = 0; row < h; row++) {
    for(int col = 0; col < w; col++) {
      cin >> mat[row][col];
    }
  }

  cout << dp(0, 0) << endl;

  return 0;
}


Measured memory_bytes: 9216
#include<cstdio>
long long int gcd(long long int x, long long int y){
	if(x<y){
		long long int z=x;
		x=y;
		y=z;
	}
	if(x%y==0)return y;
	else return gcd(y,x%y);
}
int main(){
	long long int a,b,c,d;
	scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
	long long int ans=0;
	ans+=( (b/c)-((a-1)/c) );
	ans+=( (b/d)-((a-1)/d) );
	long long int lcm=c*d/gcd(c, d);
	ans-=( (b/lcm)-((a-1)/lcm) );
	printf("%lld\n",b-a+1-ans);
	return 0;
}

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

int main() {
 int N,count = 100;
  cin >> N;
  for(int i=0;i<N;i++){
    int x,c = 0; 
    cin >> x;
    while(x%2 == 0){
      x /= 2;
      c++;
    }
    count = min(count,c);
  }
  cout << count << endl;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rp(i,n) for(int i=0; i<n; i++)
using namespace std;
using ll=long long;
typedef pair<int,int> P;
int max(int x,int y){
    if(x>y) return x;
    else return y;
}

int main(){
    int k,n;
    cin >> k >> n;
    vector<int> a(n);
    rp(i,n) cin >> a[i];
    int distance_max=0;
    rp(i,n-1){
        distance_max=max(distance_max,a[i+1]-a[i]);
    }
    distance_max=max(distance_max,k-(a[n-1]-a[0]));
    cout << k-distance_max << endl;
    return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
int n,f[2][3][3][2];
int nw=1,pst=0;
char s[2000010];
int main(){
	scanf("%s",s+1);n=strlen(s+1);
	for(int i=0;i<3;i++)f[nw][i][i][0]=1;
	for(int t=2;t<=n;t++){
		swap(nw,pst);
		memset(f[nw],0,sizeof(f[nw]));
		for(int i=0;i<3;i++)for(int j=0;j<3;j++)for(int k=0;k<2;k++){
			for(int cur=0;cur<3;cur++){
				(f[nw][(i+cur)%3][cur][(j==cur)|k]+=f[pst][i][j][k])%=998244353;
			}
		}
	}
	int tot=0,ans=1,flag=0;
	for(int i=1;i<=n;i++){
		tot+=s[i]-'a';tot%=3;
		if(i>1 && s[i]!=s[i-1])flag=1;
		if(i>1 && s[i]==s[i-1])ans=0;
	}
	if(flag==0){puts("1");return 0;}
	if(n==2){puts("2");return 0;}
	if(n==3){
		if(s[1]==s[2])puts("6");
		else {
			if(s[2]==s[3])puts("6");
			else if(s[3]==s[1])puts("7");
			else puts("3");
		}
		return 0;
	}
	//cout << n << " " << tot << endl;
	for(int i=0;i<3;i++)(ans += f[nw][tot][i][1])%=998244353;
	cout << ans << endl;
}


Measured memory_bytes: 384
n=int(input())
arr=list(map(int,input().split()))
ans=0
pos=0
cnt=0
while 1:
  if pos==n:
    break
  if arr[pos]==0:
    cnt+=1
    pos+=1
    continue
  sum=0
  xor=0
  len=0
  for i in range(pos,n):
    if arr[i]==0:
      len+=1
      continue
    sum+=arr[i]
    xor=xor^arr[i]
    if sum!=xor:
      break
    len+=1
  ans+=len*(cnt+1)+(cnt*(cnt+1))//2
  cnt=0
  pos+=1
if cnt!=0:
  ans+=(cnt*(cnt+1))//2
print(ans)

Measured memory_bytes: 23560
#include<stdio.h>
int main(){
    int a,b,c;
    
    scanf("%d %d %d",&a,&b,&c);
    if(a == b && a == c){
        printf("No");
    }else if(a != b && b != c && a != c){
        printf("No");
    }else{
        printf("Yes");
    }
    return 0;
}


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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL MOD = 1e9+7;

int main() {
    int D;
    cin >> D;
    vector<LL> c(26);
    vector<vector<LL>> s(D + 1, vector<LL>(26, 0));
    REP(i, 26) {
        cin >> c[i];
    }
    REP(i, D) {
        REP(j, 26) {
            cin >> s[i + 1][j];
        }
    }
    vector<int> last(26, 0);
    vector<int> schedule(D + 1, 0);

    LL score = 0;
    FOR(i, 1, D + 1) {
        int contest = -1;
        int satisfaction = -IINF;
        REP(j, 26) {
            LL x = s[i][j];
            REP(k, 26) {
                x -= (i - last[k])*c[k];
            }
            x += (i - last[j])*c[j];
            if(satisfaction < x) {
                satisfaction = x;
                contest = j;
            }
        }
        last[contest] = i;
        schedule[i] = contest + 1;
        score += satisfaction;
    }
    FOR(i, 1, D + 1) {
        cout << schedule[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll dfs(vector<ll> graph[],ll visit[],ll arr[],ll x)
{
	if(visit[x])
		return arr[x];
	ll len=graph[x].size(),i,y,z,maxi=0;
	for(i=0;i<len;i++)
	{
		y=graph[x][i];
		z=dfs(graph,visit,arr,y);
		maxi=max(z,maxi);
	}
	visit[x]=1;
	arr[x]=maxi+1;
	//cout<<"x and arr are "<<x<<" "<<arr[x]<<endl;
	return maxi+1;
}

int main()
{
	ll n,m;
	cin>>n>>m;
	ll arr[n+1],i,a,b,visit[n+1];
	vector<ll> graph[n+1];
	for(i=0;i<m;i++)
	{
		cin>>a>>b;
		graph[a].push_back(b);
	}
	for(i=0;i<=n;i++)
	{
		arr[i]=0;
		visit[i]=0;
	}
	for(i=1;i<=n;i++)
	{
		if(!visit[i])
			arr[i]=dfs(graph,visit,arr,i);
	}
	//for(i=1;i<=n;i++)
	//	cout<<arr[i]<<" ";
	//cout<<endl;
	sort(arr,arr+n+1);
	cout<<arr[n]-1<<endl;
	return 0;
}

Measured memory_bytes: 11392
x,y,z,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []
for xx in a:
    for yy in b:
        d.append(xx+yy)
d.sort()
d.reverse()


e = []
if len(d)>3000:
    for i in range(3000):
        for zz in c:
            e.append(d[i]+zz)
else:
    for xy in d:
        for zz in c:
            e.append(xy+zz)
e.sort()
e.reverse()

for i in range(k):
    print(e[i])


Measured memory_bytes: 151384
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1000000007;

int main(){
    int N;
    while(cin >> N){
        vector<long long> A(N);
        for(auto& t : A) cin >> t;
        long long res = 0;
        for(int i=0;i<60;i++){
            long long i0 = 0, i1 = 0;
            for(auto& t : A){
                if(t&(1LL<<i)) i1++;
                else i0++;
            }
            res += (i1*i0)%MOD*((1LL<<i)%MOD)%MOD;
            res %= MOD;
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using ll = long long;
using namespace std;

#define MOD (1000000007)

ll n;
ll sum[200005] = {};

ll solve(ll m) {
    if(m == n + 1) return 1;
    ll max, min;
    min = sum[m - 1];
    max = sum[n] - sum[n - m];
    return (max - (min - 1)) % MOD;
}

int main() {
    ll k;
    ll ans = 0;
    cin >> n >> k;

    if (n < k) {
        cout << "1" << endl;
    } else {
        for(ll i = 1;i <= n;i++) {
            sum[i] = sum[i - 1] + i;
        }
        for(ll i = k;i <= n + 1;i++) {
            ans = (ans + solve(i)) % MOD;
        }

        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 5128
#include<bits/stdc++.h>
using namespace std;
 
main()
{
   int i,j,k,sum=0,a[3][3],sum1=0;
   for(i=0;i<3;i++)
   {
       for(j=0;j<3;j++)
       {
           cin>>a[i][j];
           sum+=a[i][j];
           if(i==j)
           {
               sum1+=a[i][j];
           }
       }
   }
   if(sum%3==0)
   {
       if(sum1==(sum/3))
       {
           cout<<"Yes"<<endl;
       }
       else
       {
           cout<<"No"<<endl;
       }
   }
   else
   {
       cout<<"No"<<endl;
   }
}

Measured memory_bytes: 256
n = int(input())
l = list(map(int, input().split()))

l.sort()
count = 0
  
for i in range(0,n-2): 

    k = i + 2

    for j in range(i+1,n): 

        while (k < n and l[i] + l[j] > l[k]): 
            k += 1

        if(k>j): 
            count += k - j - 1

print(count)

Measured memory_bytes: 3188
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0]);
    let C = [];
    let S = [];
    let F = [];
    
    for(let i=1; i<N; i++) {
        let temp = arg[i].split(" ").map(n=>parseInt(n));
        C[i-1] = temp[0];
        S[i-1] = temp[1];
        F[i-1] = temp[2];
    }
    
    let answer  = [];
    
    for(let i=0; i<N; i++) {
        let time  = 0;
        time += S[i] + C[i];
        
        if(i === N - 1) {
            answer.push(0)
            break;
        }
        
        for(let j=parseInt(i)+1; j<N-1; j++) {
            if(time <= S[j]) {
                time = S[j] + C[j];
            } else {
                let temp = S[j] + F[j];
                
                while(temp < time) {
                    temp += F[j];
                }

                time = temp + C[j]; 
            }
        }
        
        answer.push(time);
    }

    console.log(answer.join("\n"))
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7868
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
    string s; cin >> s;
    rep(i, 3){
        if(s[i]=='1') s[i]='9';
        else if(s[i]=='9')s[i]='1';
    }
    cout << s<< ln;
}



Measured memory_bytes: 256
#include <cstdio>
#define ll long long
int main() {
    ll lastKnot = -1;
    ll n, l;
    ll a[100010];
    scanf("%lld", &n);
    scanf("%lld", &l);
    for (ll i = 0; i < n; i++) {
        ll tmp;
        scanf("%lld", &tmp);
        a[i] = tmp;
    }
    for (ll i = 0; i < n - 1; i++) {
        if (a[i] + a[i + 1] >= l) {
            lastKnot = i + 1;
            break;
        }
    }
    if (lastKnot == -1) {
        printf("Impossible\n");
        return 0;
    }
    printf("Possible\n");
    for (ll i = 1; i < lastKnot; i++) {
        printf("%lld\n", i);
    }
    for (ll i = n - 1; i > lastKnot; i--) {
        printf("%lld\n", i);
    }
    printf("%lld\n", lastKnot);
}


Measured memory_bytes: 1536
import fractions


N,X = map(int, input().split())
A = list(map(int, input().split()))

A.append(X)
A.sort()

diff = []
for a,b in zip(A, A[1:]):
    diff.append(b-a)

ans = diff[0]
for i in range(1,len(diff)):
    ans = fractions.gcd(ans, diff[i])


print(ans)

Measured memory_bytes: 16296
#include <iostream>
#include <stack>
using namespace std;

#define WHITE 0
#define GRAY 1
#define BLACK 2

int d[101], f[101];
int color[101] = { 0 };
int M[101][101] = { 0 };

int times;

int cur;

stack<int> s;

int search_node(int n) {
    for (int node = 1; node <= n; ++node) {
        if (M[cur][node] == 1 && color[node] == WHITE) {
            return node;
        }
    }
    return -1;      // 見つからなかった場合
}

void visit_node(int target) {
    times += 1;
    s.push(target);
    cur = s.top();
    d[cur] = times;
    color[cur] = GRAY;
}

void reversal_node() {
    // ノードを戻っていく終了時刻を記入する処理+スタック削除
    times += 1;
    s.pop();
    f[cur] = times;
    color[cur] = BLACK;
    if (s.size() != 0) {
        cur = s.top();
    } else {
        cur = 0;
    }
}

bool black_judge(int n) {        // すべて探索済みか判定，初期化
    for (int node = 1; node <= n; ++node) {
        if (color[node] != BLACK) {
            s.push(node);
            cur = node;
            color[node] = GRAY;
            d[node] = times;
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    int u, k;
    int ver;
    times = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> u >> k;
        for (int j = 1; j <= k; ++j) {
            cin >> ver;
            M[i][ver] = 1;           // 隣接行列が得られる
        }
    }

    while (true) {
        times += 1;
        if (black_judge(n)) {
            break;                  // すべて探索済みなら完了
        }
        while (s.size() != 0) {
            int target;
            target = search_node(n);
            if (target == -1) {
                reversal_node();
            } else {
                visit_node(target);
            }
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        cout << i << " " << d[i] << " " << f[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3160
s = str(input())
k = int(input())
c = 0
for i in range(len(s)):
    if s[i] == "1":
        c += 1
    else:
        break

if c >= k:
    print("1")
else:
    for i in range(len(s)):
        if s[i] != "1":
            print(s[i])
            break


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
map <int,int> M;
int A[100005];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
	{
		scanf("%d", &A[i]);
		M[A[i]];
	}
	int ctr = 0;
	for (map <int,int>::iterator it = M.begin(); it != M.end(); ++it)
	{
		it->second = ctr++;
	}
	int ans = 0;
	for (int i = 0; i < n; ++i)
	{
		int curr = i%2, fin = M[A[i]]%2;
		if(curr != fin)
			ans++;
	}
	ans/=2;
	printf("%d\n", ans);
	return 0;
}

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

// types
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

// macros
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n, m;
  cin >> n >> m;

  vector<ll> t(n);
  REP(i, n)
    cin >> t[i];

  ll ans = 0;
  REP(i, n-1){
    ll diff = t[i+1] - t[i];
    if(diff < m)
      ans += diff;
    else
      ans += m;
  }
  //count t[n-1]
  ans += m;

  cout << ans << endl;
  
  
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int a, b, d, r;
    long double f;
    cin >> a >> b;
    d = f = a / (double)b;
    r = a % b;
    cout << d << " " << r << " ";
    printf("%.8Lf\f", f);
    cout << endl;
}

Measured memory_bytes: 1240
L, R = [int(n) for n in input().split()]
ans = 2019
for i in range(L, R):
    j = i + 1
    while j <= R:
        s = i*j % 2019
        if s < ans:
            ans = s
            if ans == 0:
                break
        j += 1
    if ans == 0:
        break
print(ans)


Measured memory_bytes: 2940
#include<stdio.h>
#include<math.h>

int check(long s);

long p[500000],pc=0;

/*
struct cell{
	long node;
	struct cell *next;
};

struct cell *init;

*/

int main(void){
	long n,i,ans;
	
	
	while(scanf("%ld",&n)!=EOF){
		ans=0;
		
		for(i=2;i<=n;i+=2){
			if(check(i)==0)ans++;
			if(i==2)i-=1;
		}
		
		
		
		printf("%d\n",ans);
		
		/*
		for(i=0;i<pc;i++){
			printf("%d,",p[i]);
		}
		printf("\n\n");
		*/
	}
	return 0;
}


int check(long s){
	long i;
	//struct cell *y;
	
	if(s%2==0 && s!=2)return -1;
	
	i=sqrt(s);
	if(i*i==s)return -1;
	
	for(i=0;i<pc;i++){
		if(p[i]>sqrt(s))break;
		if(s%p[i]==0)return -1;
	}
	
	/*
	for(i=3;i*i<s;i=i+2){
		if(s%i==0)
		return -1;
	}
	*/
	
	if(s>p[pc-1] || pc==0){
		p[pc]=s;
		pc++;
	}
	
	
	return 0;
}

Measured memory_bytes: 716
use proconio::input;
use proconio::marker::Usize1;

fn main() {
    input! {
        n: usize,
        k: usize,
    }
    let mut d = vec![];
    let mut a = vec![];
    for _ in 0..k {
        input! {
            d_i: usize,
            a_i: [Usize1; d_i],
        }
        d.push(d_i);
        a.push(a_i);
    }

    let mut have = vec![false; n];
    for i in 0..k {
        for &a_ij in &a[i] {
            have[a_ij] = true;
        }
    }

    let ans = have.iter().filter(|x| !**x).count();
    println!("{}", ans);
}


Measured memory_bytes: 2188
#include <stdio.h>

int main(void){
    int i,N,A,B;
    scanf("%d %d %d",&N,&A,&B);
    int sum=0;
    for(i=1;i<=N;i++){
        int c = 0, t = i;
        for(int j = 0; j < 5;j++) c += t % 10, t /= 10;
        if(A <= c && c <= B) sum += i;
    }
    printf("%d\n",sum);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <queue>
#include <string>

using namespace std;

bool is_operator(char ch){
	return (ch == '-' || ch == '*' || ch == '+');
}

string toRPN(string str){
	string res="";
	stack<char> st;
	queue<char> que;
	for(int i=0; i<str.size(); i++){
		if(is_operator(str[i])){
			while(1){
				if(st.empty() || !is_operator(st.top()) || str[i] == '-') break;
				que.push(st.top());
				st.pop();
			}
			st.push(str[i]);
		} else if(str[i] == '('){
			st.push(str[i]);
		} else if(str[i] == ')'){
			while(!(st.top() == '(')){
				que.push(st.top());
				st.pop();
			}
			st.pop();
		} else{
			que.push(str[i]);
		}
	}

	while(!st.empty()){
		que.push(st.top());
		st.pop();
	}
	while(!que.empty()){
		res += que.front();
		que.pop();
	}
	return res;
}

int main(){
	while(1){
		string str; cin >> str;
		if(str == ".") break;
		str = toRPN(str);

		int ans=0;
		for(int p=0; p<3; p++){
			for(int q=0; q<3; q++){
				for(int r=0; r<3; r++){
					stack<int> st;
					for(int i=0; i<str.size(); i++){
						if(str[i] == 'P') st.push(p);
						else if(str[i] == 'Q') st.push(q);
						else if(str[i] == 'R') st.push(r);
						else if(isdigit(str[i])) st.push(str[i]-'0');
						else if(str[i] == '-'){
							int x = st.top();
							st.pop();
							st.push(2-x);
						} else if(str[i] == '*'){
							int x = st.top(); st.pop();
							int y = st.top(); st.pop();
							st.push(min(x, y));
						} else if(str[i] == '+'){
							int x = st.top(); st.pop();
							int y = st.top(); st.pop();
							st.push(max(x, y));
						}
					}
					if(st.top() == 2) ans++;
					st.pop();
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3156
#n = int(input())
#n,k = map(int,input().split())
#x = list(map(int,input().split()))

n = int(input())
a = [-1 for i in range(n)]

for i in range(n):
    memo = int(input())-1
    if a[i] == -1:
        a[i] = memo

ans = [False for i in range(n)]

trg = 0
cnt = 0
for i in range(n):
    
    memo2 = a[trg]

    if trg == 1:
        print(cnt)
        ans[1] = True
        break

    if not(ans[memo2]):
        ans[memo2] = True
        trg = memo2
        cnt += 1

    
    else:
        break

if not(ans[1]):
    print(-1)










Measured memory_bytes: 7860
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	int num, h, i, a, maxa = 0, ans = 0;
	cin >> num >> h;
	vector<int> b(num);
	for (i = 0; i < num; i++) {
		scanf("%d%d", &a, &b[i]);
		maxa = max(maxa, a);
	}
	sort(b.begin(), b.end(), greater<int>());
	for (i = 0; i < num; i++) {
		if (maxa > b[i] || h <= 0)
			break;
		h -= b[i];
		ans++;
	}
	if (h > 0) {
		ans += h / maxa;
		if (h % maxa > 0)
			ans++;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>

int main()
{
  std::string s;
  std::cin >> s;
  
  int begin, end;
  int len = s.size();
  for ( int i = 0; i < len; i++ ) {
    if ( s[i] == 'A' ) {
      begin = i;
      break;
    }
  }
  for ( int i = len; i > 0; i-- ) {
    if ( s[i] == 'Z' ) {
      end = i;
      break;
    }
  }

  std::cout << end - begin + 1 << std::endl;
  return 0;
}


Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
int n;
int a[200000];
long long s,s1,s2;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		s+=(LL)a[i];
		a[n+i]=a[i]=2*a[i];
	}
	int k=n/2,i,j;
	for(i=2,j=1;j<=k;i+=2,j++)
		s1+=(LL)a[i],s2+=(LL)a[i+1];
	printf("%lld %lld",s-s1,s-s2);
	int j1=i,j2=i+1;
	for(int i=3;i<=n;i++)
	{
		long long ans;
		if(i%2)ans=s1=s1+a[j1]-a[j1-k*2],j1+=2;
		else ans=s2=s2+a[j2]-a[j2-k*2],j2+=2;
		printf(" %lld",s-ans);
	}
}

Measured memory_bytes: 2048
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll  long long 
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e7+9;
const ll MOD=1e9+7;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int main() 
{

	  ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int n;
    cin>>n;
    int cnt=0;
    int arr[n+1];
    memset(arr, 0 , sizeof(arr));
    for(int i=1;i<=sqrt(n);i++)
    {
      for(int j=1;j<=sqrt(n);j++){
        for(int k=1;k<=sqrt(n);k++){
          int now=(i*i)+(j*j)+(k*k)+(i*k)+(i*j)+(j*k);
          if(now>n)
            continue;
          arr[now]=arr[now]+1;
        }
      }
    }
    for(int i=1;i<=n;i++)
      cout<<arr[i]<<endl;
}

Measured memory_bytes: 3696
fun main(args: Array<String>) {
    abc115c()
}

/*
 木をソート → 一番左からN本選んでmax-minを計算 を右にずらしていって全部探索 → その最小値を求める
 */

fun abc115c() {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }
    val treeHeights = (1..n).map { readLine()!!.toLong() }

    val sortedTreeHeights = treeHeights.sorted()

    val answer = (0..(n - k)).map {
        val minHeight = sortedTreeHeights[it]
        val maxHeight = sortedTreeHeights[it + k - 1]
        maxHeight - minHeight
    }.min()

    println(answer)
}


Measured memory_bytes: 46724
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>

using namespace std;
typedef long long ll;

int main() {
  int N;
  cin >> N;
  vector<int> h(N);
  for (int i = 0; i < N; ++i) {
    cin >> h[i];
  }
  int ans = 0;
  int cur = 0;
  for (int i = 1; i < N; ++i) {
    if (h[i] <= h[i - 1]) {
      ++cur;
      ans = max(ans, cur);
    } else {
      cur = 0;
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(n) ((int)(n).size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int a[110][110];

int main(){FIN;
  int n; cin >> n;
  fore(i,0,n) fore(j,0,n) a[i][j]=i!=j;
  if(n%2==0){
    fore(i,0,n) a[i][n-1-i]=0;
  }
  else{
    fore(i,0,n-1) a[i][n-2-i]=0;
  }
  int am=0;
  fore(i,0,n) fore(j,i+1,n) am+=a[i][j];
  cout << am << "\n";
  fore(i,0,n) fore(j,i+1,n) if(a[i][j]) cout << i+1 << " " << j+1 << "\n";
}

Measured memory_bytes: 384
N, A, B = list(map(int, input().split()))

number_list = list(map(str, range(1, N+1)))

count = 0

for number in number_list:
    sum = 0
    for s in number:
        sum += int(s)
    if sum >= A and sum <= B:
        count += int(number)

print(count)


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int64 gcd(int64 a, int64 b){
    if(a % b == 0)return b;
    return gcd(b, a % b);
}

int64 lcm(int64 a, int64 b){
    return a * b / gcd(a, b);
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int64 a,b;
    cin >> a >> b;
    cout << lcm(a, b) << endl;
    return 0;
}

Measured memory_bytes: 256
def selection_sort(a, n):
    sw_num = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j] < a[minj]:
                minj = j
        if i != minj:
            tmp = a[i]
            a[i] = a[minj]
            a[minj] = tmp
            sw_num += 1

    return sw_num


n = int(input())
a = [int(i) for i in input().split()]

sw_num = selection_sort(a, n)

print(' '.join([str(i) for i in a]))
print(sw_num)


Measured memory_bytes: 5608
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back

#define y0 pmt
#define y1 pmtpmt
#define x0 pmtQAQ
#define x1 pmtQwQ

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int > vi;
typedef pair<int ,int > pii;
typedef vector<pii> vii;
const int inf=0x3f3f3f3f, maxn=3000007;
const ll mod=998244353;
const ll linf=0x3f3f3f3f3f3f3f3fLL;
const ll P=998244353;
ll n,A,B,k;
ll f[maxn],g[maxn],d[maxn];
ll qpow(ll a,ll b){
	ll rt=1;
	while(b){
		if(b&1)rt=(rt*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return rt;
}

ll C(ll n,ll m){
	if(n<m)return 0;
	return (f[n]*g[m]%mod*g[n-m]%mod);
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	f[0]=1;
	for(int i=1;i<=3000000;i++)f[i]=f[i-1]*i%mod;
	g[3000000]=qpow(f[3000000],mod-2);
	for(int i=3000000;i>=1;i--)g[i-1]=g[i]*i%mod;
	scanf("%lld%lld%lld%lld",&n,&A,&B,&k);
	ll ans=0;
	for(ll i=0;i<=n;i++){
		if((k-i*A)%B!=0)continue;
		ll j=(k-i*A)/B;
		(ans+=C(n,i)*C(n,j)%mod)%mod;
	}
	printf("%lld",ans%mod);
	return 0;
}


Measured memory_bytes: 48000
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define ff first
#define ss second
#define nl '\n'
//////////////////////////////////////////////////



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

  ll x, y;
  cin >> x >> y;
  if( x % y == 0 ) cout << -1 << nl;
  else cout << x << nl;

  return 0;
}
/* -*- -*- */


Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

string S;
int num[4];

pair<int, string> func(int i, int x, string eq) {
	if (i == 4) {
		if (x == 7) {
			cout << eq + "=7" << endl;
			exit(0);
		}
		else return { x, eq };
	}

	auto sum1 = func(i + 1, x + num[i], eq + "+" + to_string(num[i]));
	if (sum1.first == 7) return sum1;

	auto sum2 = func(i + 1, x - num[i], eq + "-" + to_string(num[i]));
	if (sum2.first == 7) return sum2;

	return {0, ""};
}


int main() {
	cin >> S;
	for (int i = 0; i < 4; ++i) {
		num[i] = S[i] - '0';
	}

	auto sum = func(1, num[0], S.substr(0, 1));
	cout << sum.second + "=7" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define SYNC ios::sync_with_stdio(false); cin.tie(NULL); cerr.tie(NULL);
using namespace std;
int main(){
  SYNC;
  int n,min=INT_MAX,ind=0,ans=INT_MAX;
  double k;
  cin >> n >> k;
  int a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<min){
      min=a[i];
      ind=i+1;
    }
  }
  int temp1=ind-k,temp2=ind;
  if(temp1<=0) temp1=1;
  while(temp1<=temp2){
    double b=n,a=1;
    double count=ceil((b-temp1)/(k-1))+ceil((temp1-a)/(k-1));
    if(int(count)<ans){
      ans=count;
    }
    temp1++;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string S;
  int n,count=0;
  cin>>S;
  n=S.size();
  for(int i=0;i<n/2;i++){if(S.at(i)!=S.at(n-1-i))count++;}
  cout<<count<<endl;
}

Measured memory_bytes: 256
loop do
  h, w = gets.split.map(&:to_i)
  break if h.zero? && w.zero?

  even_line = (0...w).map { |i| i.even? ? '#' : '.' }.join
  odd_line  = (0...w).map { |i| i.even? ? '.' : '#' }.join

  h.times do |i|
    line = i.even? ? even_line : odd_line
    puts line
  end
  puts
end

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

int main(){
 int n;
 string s,t;
 cin >> n;
 cin >> s >> t;
 string sum;
 for(int i=0; i<n; i++){
     sum +=s[i];
     sum = sum+t[i];
 }
 cout << sum << endl;

  return 0;
}

 


Measured memory_bytes: 768
s = input()
def kaibun(s):
    return all([s[i] == s[-(i + 1)] for i in range(int(len(s) / 2))])
n = len(s)

print("Yes" if kaibun(s) & kaibun(s[0:int((n-1) / 2)]) & kaibun(s[int(n+3/2)-1:]) else "No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
vector<int> v[200100];
vector<bool> fl(200100);
vector<int> ans(200100);
vector<int> a(200100);
void rec(int node,int val){
    if(fl[node]){
        return;
    }
    fl[node] = true;
    val+=a[node];
    ans[node] = val;
    for(auto i:v[node]){
        rec(i,val);
    }
    return;
}
int main(){
    int n,m;
    cin >> n >> m;
    rep(i,n-1){
        int x,y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    rep(i,m){
        int x,y;
        cin >> x >> y;
        a[x]+=y;
    }
    rec(1,0);
    rep(i,n){
        cout << ans[i+1] << ' ';
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 21120
# AtCoderでは、コンテストに参加すると「色」が付き、これはレートによって次のように変化します：
# レート 1-399：灰色
# レート 400-799：茶色
# レート 800-1199：緑色
# レート 1200-1599：水色
# レート 1600-1999：青色
# レート 2000-2399：黄色
# レート 2400-2799：橙色
# レート 2800-3199：赤色
# また、レートが 3200 以上になると色を自由に変えることができます。
# 現在 N 人の人がAtCoderのコンテストに参加したことがあり、i 人目の人のレートは ai です。
# そのとき、色の種類数の最小値と最大値を求めなさい。

n = gets.to_i
input_a = gets.chomp.split

a = Array.new
n.times do |i|
    a << input_a[i].to_i
end

def color(rate)
    case rate
    when 1..399
        return "灰色"
    when 400..799
        return "茶色"
    when 800..1199
        return "緑色"
    when 1200..1599
        return "水色"
    when 1600..1999
        return "青色"
    when 2000..2399
        return "黄色"
    when 2400..2799
        return "橙色"
    when 2800..3199
        return "赤色"
    else
        return "自由"
    end
end

a_colors = Array.new
freedom_color_count = 0

a.each do |rate|
    if !a_colors.include?(color(rate))
        a_colors << color(rate)
    end

    if color(rate) == "自由"
        freedom_color_count += 1
    end
end

if freedom_color_count != 0
    max = a_colors.length - 1
    min = a_colors.length - 1
    if min == 0
        min += 1
    end

    while freedom_color_count > 0
        max += 1
        freedom_color_count -= 1
    end
else
    max = a_colors.length
    min = a_colors.length
end

print min.to_s + " " + max.to_s + "\n"

Measured memory_bytes: 1916
import bisect

A,B,Q=map(int,input().split())
inf = 10 ** 18
S = [-inf] + [int(input()) for _ in range(A)] + [inf]
T = [-inf] + [int(input()) for _ in range(B)] + [inf]

for q in range(Q):
    x = int(input())
    s_h = bisect.bisect(S,x)
    s_l = s_h - 1
    t_h = bisect.bisect(T,x)
    t_l = t_h - 1

    ans = inf
    for s in [S[s_l],S[s_h]]:
        for t in [T[t_l],T[t_h]]:
            d1 = abs(s-x)+abs(t-s)
            d2 = abs(t-x)+abs(s-t)
            ans = min(ans,d1,d2)
    
    print(ans)


Measured memory_bytes: 12800
#include "bits/stdc++.h"
using namespace std;
 
#define REP(i, n) for(ll i = 0;i < n;i++)
#define REP1(i, n) for(ll i = 1;i < n;i++)
#define REPR(i, n) for(ll i = n-1;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
 
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())
 
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
 
#define pb(a) push_back(a)
 
int n,m;
 
 
int main(){
  ll ans=0LL;
  cin >> n >> m;
  vector<ll> a(n),b(m),c(m);
  REP(i,n) cin>>a[i];
  REP(i,m){
    cin>>b[i]>>c[i];
  }
 
  vector<ll> d(m);
  REP(i,m){
    d[i]=c[i]*100001LL+b[i];
  }
  sort(d.begin(), d.end(),greater<ll>());
  REP(i,m){
    c[i]=d[i]/100001LL;
    b[i]=d[i]%100001LL;
  }
  sort(a.begin(), a.end());
 
 
  
  int okikaem=0;
  int okikaem2=0;
  REP(i,m){
    okikaem2=okikaem+b[i];
    if (okikaem2>n){
      okikaem2=n;
      b[i]=okikaem2-okikaem;
    }
    if (a[okikaem2-1]<=c[i]){
      ans+=b[i]*c[i];
      okikaem=okikaem2;
      if (okikaem==n)break;
    }else{
      REP(j,b[i]){
        if (a[okikaem]<=c[i]){
          ans+=c[i];
          okikaem++;
          if (okikaem==n)break;
        }else{
          break;
        }
      }
      break;
    }
  }
  for(int i=okikaem;i<n;i++){
    ans+=a[i];
  }
 
  cout<<(ans)<<endl;
 
  return 0;
}

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

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

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);
ll a[200005];

int main(){
  int n;
  ll l=0, r=0;
  cin >> n;
  REP(i, n) cin >> a[i];
  ll tmp_sum=0;
  ll tmp_xor=0;
  ll res=0;
  while(r<=n){
    while(tmp_sum==tmp_xor and r<=n){
      tmp_sum += a[r];
      tmp_xor ^= a[r];
      r++;
    }
    res += (r-l-1)*(r-l)/2;
    while(tmp_sum!=tmp_xor){
      tmp_sum -= a[l];
      tmp_xor ^= a[l];
      l++;
    }
    if(r!=n+1) res -= (r-l-1)*(r-l)/2;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 1920
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, begin, end) for(ll i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(ll i=(begin)-1;i>=(end);i--)
#define IREP(i, n) IFOR(i,n,0)
#define SORT(a) sort(a.begin(), a.end())
#define ISORT(a) sort(a.begin(), a.end(),greater<ll>())
#define REVERSE(a) reverse(a.begin(), a.end())
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=(" << v[0]; FOR(i_debug, 1, v.size()){ cout << "," << v[i_debug]; } cout << ")" << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;}
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)

#define ll long long
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 1000000000000000000

using vec = vector<ll>;
using mat = vector<vec>;
using Pii = pair<ll, ll>;
using PiP = pair<ll, Pii>;
using PPi = pair<Pii, ll>;
using bvec = vector<bool>;
using Pvec = vector<Pii>;


template<typename T> void readv(vector<T> &a) { REP(i, a.size()) cin >> a[i]; }
void readv_m1(vector<int> &a) { REP(i, a.size()) {cin >> a[i]; a[i]--;} }

ll mod = 1000000007;


int main()
{
	ll N;
	cin >> N;
	vec d(N);
	REP(i, N) {
		cin >> d[i];
	}

	SORT(d);

	ll ans = d[N / 2] - d[N / 2 - 1];
	cout << ans << endl;

	return 0;
}

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


int main() {
    int N;
    cin >> N;
    
    int ans=N, M, cnt=0, m=0;
    for(int i=N; i>0; i--){
        M = i; cnt=0;
        while(1){
            if(M%2==0){
                M /= 2;
                cnt++;
            }
            else{
                break;
            }
        }
        if(m<cnt){
            m=cnt;
            ans=i;
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.1415926535897
using namespace std;
typedef long long ll;

int main(void)
{
    vector<int> antena(5, 0);
    int distance;
    for (int i = 0; i < 5; i++)
    {
        cin >> antena.at(i);
    }
    cin >> distance;

    bool is_connected = true;
    for (int i = 0; i < 4; i++)
    {
        for (int j = i + 1; j < 5; j++)
        {
            if (abs(antena.at(i) - antena.at(j)) > distance)
            {
                is_connected = false;
            }
            if (is_connected == false)
            {
                break;
            }
        }
        if (is_connected == false)
        {
            break;
        }
    }

    if (is_connected == true)
    {
        cout << "Yay!" << endl;
    }
    else
    {
        cout << ":(" << endl;
    }

    return (0);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int64_t h; cin>>h;
  int64_t num=1,ans=0;
  while(h){
    ans+=num;
    if(h==1) break;
    else{
       h/=2;
       num*=2;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		int red = 0;
		int blue = 0;
		for (int i = 0; i < n; i++) {
			if (s.charAt(i) == 'R') {
				red++;
			} else {
				blue++;
			}
		}
		if (red > blue) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i,a,b) for (int i = a; i <b; i++)
typedef long long ll;
#define int ll
typedef vector<int> vi;
typedef vector<long long> vl;
typedef pair<int,int> pi;
#define trace(x) cout<<#x<<"="<<x<<"\n";
#define llp 1000000007
#define mod 1000000007

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}

template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    typename vector< T > :: const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "}";
}

template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    typename set< T > :: const_iterator it;
    for ( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << *it;
    }
    return os << "]";
}

template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    typename map< F , S >::const_iterator it;
    for( it = v.begin(); it != v.end(); it++ ) {
        if( it != v.begin() ) os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]";
}

#define deb(x) cerr << #x << " = " << x << endl;

vector<pair<int, int > >adj[100005];
vector<int>col;
int dis[100005];
void dfs(int x, int p){
    for(auto g:adj[x]){
        if(g.F!=p){
            dis[g.F]=dis[x]+g.S;
            if(dis[g.F]%2==0){
                col[g.F]=0;
            }
            else{
                col[g.F]=1;
            }
            dfs(g.F,x);
        }
    }
}


int32_t main(){
	ios::sync_with_stdio(false);
    int n;
    cin>>n;
    memset(dis,0,sizeof(dis));
    col.resize(n+1);
    REP(i,0,n-1){
        int A, B, C;
        cin>>A>>B>>C;
        adj[A].push_back({B,C});
        adj[B].push_back({A,C});
    }
    col[1]=0;
    dfs(1,0);
    REP(i,1,n+1){
        cout<<col[i]<<"\n";
    }



	return 0;
}

Measured memory_bytes: 11008
/**
 *	Author: houtaru
 *	Create: 27.05.2018 20:58:42
 */

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;

int n;
int a[maxn];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    long long answer = 0;;
    for (int i = 1, j = 1, cur = 0; i <= n; ++i) {
        while (j <= n && ((cur & a[j]) == 0)) cur += a[j++];
        answer += j - i;
        cur -= a[i];
    }
    printf("%lld\n", answer);
    return 0;
}

Measured memory_bytes: 1024