akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int main()
{
    long long int a,b,k,s,d;
    scanf("%lld %lld",&a,&b);
    k=(a+b)/2;
    s=abs(a-k);
    d=abs(b-k);
    if(s==d)
    {
        printf("%lld",k);
    }
    else
        printf("IMPOSSIBLE");

}


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

using i64 = long long int;

int main(){
    i64 n;
    cin >> n;
    vector<i64> v;
    i64 sum = 0;
    for(int i=0;i<n;++i){
        i64 a;
        cin >> a;
        v.push_back(a);
        sum += a;
    }

    if(sum % (n*(n+1)/2) != 0)cout << "NO" << endl;
    else{
        i64 cnt = sum / (n*(n+1)/2);
        bool ng = false;
        for(int i=0;i<n-1;++i){
            i64 d = v[i] - v[i+1];
            if(abs(cnt+d) % n != 0 || (cnt+d) / n < 0){
                ng = true;
                break;
            }
        }
        if(ng)cout << "NO" << endl;
        else cout << "YES" << endl;
    }

    return 0;
}


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

int main() {
  int N; cin >> N;
  vector<int> A(N-1);
  rep(i,N-1) cin >> A[i];

  vector<int> R(N);
  rep(i,N) R[i] = 0;
  
  rep(i,N-1) {
    R[A[i]-1]++;
  }
  rep(i,N) {
    cout << R[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 4844
import kotlin.system.exitProcess

fun main(args: Array<String>) {
    readLine()
    val nums = readLine()!!.split(" ").map { it.toBigDecimal() }.toMutableList()

    var ans = 1.toBigDecimal()

    // 0考慮
    if (nums.contains(0.toBigDecimal())) {
        print("0")
        exitProcess(0)
    }

    for (num in nums) {
        ans *= num

        // 早めに切り上げる
        if (ans > 1000000000000000000.toBigDecimal()) {
            println("-1")
            exitProcess(0)
        }
    }

    if (ans > 1000000000000000000.toBigDecimal()) {
        println("-1")
    } else {
        println(ans)
    }
}


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

int main() {
  int H, W;
  cin >> H >> W;
  string S = "";
  
  vector<char> vec(W+2, '#');
  
  for (int i = 0; i < W+2; i++) {
    S += vec.at(i);
  }
    cout << S << endl;
  S = "";
  
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> vec.at(j+1);
    }
    for (int k = 0; k < W+2; k++) {
      S += vec.at(k);
    }
      cout << S << endl;
      S = "";
  }
  
  for (int i = 0; i < W+2; i++) {
    vec.at(i) = '#';
  }
  for (int i = 0; i < W+2; i++) {
    S += vec.at(i);
  }
    cout << S << endl;
}


Measured memory_bytes: 256
N, M, K = map(int, input().split())
MOD = 998244353

C = [1]
for i in range(N):
    if i == 0:
        C.append(M)
    else:
        C.append((C[i] * (M-1)) % MOD)

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % MOD )
    inverse.append( ( -inverse[MOD % i] * (MOD//i) ) % MOD )
    g2.append( (g2[-1] * inverse[-1]) % MOD )


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


ans = 0
for i in range(K + 1):
    ans += cmb(N-1, i, MOD) * C[N-i] % MOD

if M == 1:
    if N - 1 <= K:
        print(1)
    else:
        print(0)
elif N == 1:
    print(M)
else:
    print(ans % MOD)


Measured memory_bytes: 114196
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <functional>
#include <algorithm>
using namespace std;

struct edge{ int from, to ,cost; };
//typedef pair<int, int > P;
//typedef pair<double, P> S;

const double INF = 9999999.0;
const double EPS = 1e-5;

int n, m, p, a, b, st, gl;

int t[8];
double dp[31][1 << 8];

int main()
{
    while(cin >> n >> m >> p >> a >> b && ( n || m || p || a || b)) {

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

        vector<vector<edge> > es(m+1);
        
        int x, y, z;
        for(int i = 0; i < p; i++) {
            cin >> x >> y >> z;
            es[x].push_back((edge){x, y, z});
            es[y].push_back((edge){y, x, z});
        }
        
        for(int i = 1; i <= m; i++) 
            for(int k = 0; k < (1 << n); k++) 
                dp[i][k] = INF;
        
        double ans = INF;
        dp[a][(1 << n) - 1] = 0.0;
        for(int S = (1 << n) - 1; S >= 0; S--) {
            ans = min(ans, dp[b][S]);
            for(int v = 1; v <= m; v++) {
                for(int i = 0; i < n; i++) {
                    if ((1 << i) & S) {
                        for(int u = 0; u < es[v].size(); u++) {
                            int to = es[v][u].to;
                            //cout << v << " => " << to << endl;
                            dp[to][S & ~(1 << i)] = min(dp[to][S & ~(1 << i)], dp[v][S] + (double)es[v][u].cost / t[i]);
                        }
                    }
                }
            }
        }

        if(ans + EPS > INF)
            cout << "Impossible" << endl;
        else
            printf("%.3lf\n", ans);

    }
}

Measured memory_bytes: 1040
#include<bits/stdc++.h>
using namespace std;
int a,b;
int main(){
	scanf("%d %d",&a,&b);
	int l=max(-1000000,b-a+1),r=min(1000000,b+a-1);
	for(int i=l;i<=r;++i)printf("%d ",i);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include<math.h>
using namespace std;
#define int long long int
#define pp pair<int,int>
#define endl "\n"
#define PI 3.14159265
int MAXN = 5000001;
const int mod=1000000007;
const int INF =INT_MAX;
inline int gcd(int a,int b){if(a==0) return b;return gcd(b%a,a);}
inline int pow(int a,int n,int mod){if(n==0)return 1;int p=pow(a,n/2,mod);p=(p%mod*p%mod)%mod;if(n%2) return (p%mod*a%mod)%mod;else return p;}
int func(int arr[], int n)
{
    int high = 0;
    for (int i = 0; i < n; i++)
        high = max(high, arr[i]);
    int divisors[high + 1] = { 0 };
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j <= sqrt(arr[i]); j++)
        {
            if (arr[i] % j == 0)
            {
                divisors[j]++;
                if(j!=1&&divisors[j]>1)return -1;
                if (j != arr[i] / j)
                   {
                       divisors[arr[i] / j]++;
                      if((arr[i]/j)!=1&&divisors[arr[i] / j]>1)return -1;

                   }
            }
        }
    }
    for (int i = high; i >= 1; i--)
        if (divisors[i] > 1)
            return i;
}
int func1(int arr[], int n)
{
    int result = arr[0];
    for (int i = 1; i < n; i++)
    {
        result = __gcd(arr[i], result);

        if(result == 1)
        {
           return 1;
        }
    }
    return result;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin>>t;
    while(t--)
    {
      int n;
      cin>>n;
      int v[n];
      for(int i=0;i<n;i++)cin>>v[i];
      if(func(v,n)==1)
        cout<<"pairwise coprime"<<endl;
      else if(func1(v,n)==1)cout<<"setwise coprime"<<endl;
        else cout<<"not coprime"<<endl;
    }
    return 0;
}


Measured memory_bytes: 19176
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
a = inpl()
sign = [-1]*n

pre = -1
for i in range(1,n):
    if a[i] > a[i - 1]:
        sign[i] = 1
        pre = 1
    elif a[i] < a[i - 1]:
        sign[i] = -1
        pre = -1
    else:
        sign[i] = pre

money = 1000
stock = 0
for i in range(n):
    if sign[i] == 0 or (i != n-1 and sign[i] == sign[i + 1]):
        continue

    if sign[i] == 1:
        #売る
        money += a[i] * stock
        stock = 0
    elif sign[i] == -1:
        flg = False
        if [j for j in sign[i:] if j == 1]:
            flg = True
        #買う
        if flg == True:
            buy =  money // a[i]
            stock += buy
            money -= a[i] * buy
print(money)

Measured memory_bytes: 31144
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		String str;
		int Y = 0;

		for (int i = 0; i < N; i++) {
			str = s.next();
			if (str.equals("Y")) {
				Y++;
			}
		}
		if (Y == 0) {
			System.out.println("Three");
		} else {
			System.out.println("Four");
		}
	}
}

Measured memory_bytes: 21716
#include<stdio.h>
   int main(void){
   int a,b,c,n;
   while(scanf("%d%d",&a,&b) !=EOF){
      c = a + b;
      if(c<10)
         printf("1\n");
      else if(c<100)
         printf("2\n");
      else if(c<1000)
         printf("3\n");
      else if(c<10000)
         printf("4\n");
      else if(c<100000)
         printf("5\n");
      else if(c<1000000)
         printf("6\n");
      else
         printf("7\n");
      }
   return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
using namespace std;
int main() {
    #ifdef DEBUG
    std::ifstream in("/home/share/inputf.in");
    std::cin.rdbuf(in.rdbuf());
    #endif
    string S;
    cin >> S;
    int ans0 = 0, ans1 = 0;
    for(int i = 0; i < S.size(); i++) {
        int s = S[i] == '0';
        if(s == (i & 1)) {
            ans0++;
        } else {
            ans1++;
        }
    }
    cout << min(ans0, ans1) << endl;
    return 0;
}

Measured memory_bytes: 512
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 2e5 + 10;
int a[N];
int getans(int x, int y)
{
	if (x * y >= 0) return max(abs(x), abs(y)) * 2;
	else return abs(y - x) * 2;
}
int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		ans += abs(a[i] - a[i - 1]);
	}
	ans += abs(a[n]);
	for (int i = 1; i <= n; i++)
	{
		printf("%d\n", ans - abs(a[i] - a[i - 1]) - abs(a[i + 1] - a[i]) + abs(a[i + 1] - a[i - 1]));
	}
	return 0;
}


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

using namespace std;

const int maxN = 1e2+10;
int M, N, Q, A[maxN], ans[maxN][maxN];

int main()
{
    cin >> M >> N;
    cin >> Q;
    int x = 1, y = 1, d = 0;
    for (int i=1,k; i <= Q; i++)
    {
        cin >> k;
        while (k--)
        {
            ans[x][y] = i;
            if (!d) y++;
            else y--;
            if (y > N) x++, y = N, d = 1;
            if (y < 1) x++, y = 1, d = 0;
        }
    }
    for (int i=1; i <= M; i++)
    {
        for (int j=1; j <= N; j++) cout << ans[i][j] << " ";
        puts("");
    }
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n - 1];
        int manzokudo = 0;

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        for (int i = 0; i < n - 1; i++) {
            c[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) { // a[i]番目の料理を食べる
            manzokudo += b[a[i] - 1]; //満足度
            if (i != 0 && a[i - 1] + 1 == a[i]) {
                manzokudo += c[a[i]-2];
            }
        }

        System.out.println(manzokudo);
    }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define lb(x) ((x)&(-(x)))
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int> 
#define dalao 1000000007
#define inf 0x3f3f3f3f
#define N 405
using namespace std;
typedef long long ll;
int n,c,a[N],b[N],p[N][N],f[N][N],s[N][N];
inline int pw(int a,int b){int r=1;for(;b;b>>=1,a=1ll*a*a%dalao)if(b&1)r=1ll*r*a%dalao;return r;}
int main(){
	cin>>n>>c;
	for(int i=1;i<=400;i++)for(int j=0;j<=400;j++)p[i][j]=pw(i,j),s[i][j]=(s[i-1][j]+p[i][j])%dalao;
	for(int i=1;i<=n;i++)cin>>a[i];
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		cin>>b[i];
/*		for(int x=a[i];x<=b[i];x++)for(int j=0;j<=c;j++){
			for(int k=0;k<=j;k++)(f[i][j]+=1ll*f[i-1][j-k]*pw(x,k)%dalao)%=dalao;
		}*/
		for(int j=0;j<=c;j++)for(int k=0;k<=j;k++)(f[i][j]+=1ll*f[i-1][j-k]*(s[b[i]][k]-s[a[i]-1][k]+dalao)%dalao)%=dalao;
	}
	cout<<f[n][c];
	
	return 0;
}
//3 100 7 6 5 9 9 9

Measured memory_bytes: 2176
#include <iostream>

using namespace std;

typedef unsigned long long ull;

ull N,K,V[101],W[101];
ull dp[100001];

int main()
{
    cin>>N>>K;

    for(ull i = 1; i<=N; i++){
        cin>>W[i]>>V[i];
    }

    for(ull i = 1; i<=N; i++){ //pilih barang
        for(ull j = K; j>0; j--){
            if(j >= W[i]){
                dp[j] = max(dp[j],dp[j-W[i]] + V[i]);
            }
        }
    }

    cout<<dp[K]<<endl;
    return 0;
}


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

int main(int argc, char const* argv[])
{
    int N;
    cin >> N;

    int n;
    int counter = 0;
    int temp;
    int ans = 1;

    for (int i = 1; i <= N; i++) {
        n = i;
        temp = 0;
        while ((n % 2) == 0) {
            n = (n / 2);
            temp += 1;
        }
        if (temp > counter) {
            counter = temp;
            ans = i;
        }
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int CM = 1 << 17, CL = 12;
char cn[CM + CL], * ci = cn + CM + CL, * owa = cn + CM, ct;
const ll ma0 = 1157442765409226768;
const ll ma1 = 1085102592571150095;
const ll ma2 = 71777214294589695;
const ll ma3 = 281470681808895;
const ll ma4 = 4294967295;
inline int getint() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = 68 - __builtin_ctzll((tmp & ma0) ^ ma0);
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += 72 - dig >> 3;
	return tmp;
}
inline int getintA() {
	if (ci - owa > 0) {
		memcpy(cn, owa, CL);
		ci -= CM;
		fread(cn + CL, 1, CM, stdin);
	}
	ll tmp = *(ll*)ci;
	int dig = ((tmp & ma0) ^ ma0) ? 68 - __builtin_ctzll((tmp & ma0) ^ ma0) : 0;
	tmp = tmp << dig & ma1;
	tmp = tmp * 10 + (tmp >> 8) & ma2;
	tmp = tmp * 100 + (tmp >> 16) & ma3;
	tmp = tmp * 10000 + (tmp >> 32) & ma4;
	ci += (64 - dig >> 3);
	while ((ct = *ci++) >= '0') tmp = tmp * 10 + ct - '0';
	return tmp;
}
char dn[1300000], *di = dn;
inline void putint(int X) {
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--)* di++ = (*(C + i));
	*di++ = '\n';
}
int N;
int A[200001];
int E[400001], ne[400001], he[200001], it[200001];
int V[200001], v;
int S[200001], s;

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

	N = getint();
	rep1(i, N) A[i] = getintA();
	int k = 1;
	rep(i, N - 1) {
		int u = getint(), v = getint();
		E[k] = v;
		ne[k] = he[u];
		he[u] = k++;
		E[k] = u;
		ne[k] = he[v];
		he[v] = k++;
	}

	V[v++] = 2000000000;
	S[s++] = 1;
	while (s) {
		int p = S[s - 1];
		if (p > 0) {
			S[s - 1] = -p;
			if (V[v - 1] < A[p]) {
				it[p] = v;
				swap(V[v++], A[p]);
				for (auto to = he[p]; to; to = ne[to]) {
					if (he[E[to]] > 0) {
						S[s++] = E[to];
					}
				}
			}
			else {
				it[p] = lower_bound(V, V + v, A[p]) - V;
				swap(V[it[p]], A[p]);
				for (auto to = he[p]; to; to = ne[to]) {
					if (he[E[to]] > 0) {
						S[s++] = E[to];
					}
				}
			}
			he[p] = -v;
		}
		else {
			s--;
			p = -p;
			V[it[p]] = A[p];
			v -= !A[p];
		}
	}

	rep1(i, N) putint(-he[i]);
	fwrite(dn, 1, di - dn, stdout);

	Would you please return 0;
}

Measured memory_bytes: 8692
q = int(input())
 
MASK = (1 << 64) -1

mask = []
for i in range(q):
    retmask = 0
    ret = [i for i in map(int,input().split())]
    for i in range(1,ret[0]+1):
        retmask += 1 << ret[i]
    mask.append(retmask)

q = int(input())
n = 0
for i in range(q):
    query = [i for i in map(int,input().split())]
    if query[0] == 0:
        temp = 1 << query[1]
        if (n & temp) == 0:
            print(0)
        else:
            print(1)
 
    elif query[0] == 1:
        n = (n | mask[query[1]])
 
    elif query[0] == 2:
        n = n & (~ mask[query[1]] & MASK)
         
    elif query[0] == 3:
        n = n ^ mask[query[1]]
         
    elif query[0] == 4:
        if n & mask[query[1]] == mask[query[1]]:
            print(1)
        else:
            print(0)

        
            
    elif query[0] == 5:
        if n & mask[query[1]] > 0:
            print(1)
        else:
            print(0)
             
    elif query[0] == 6:
        if n & mask[query[1]] == 0:
            print(1)
        else:
            print(0)
            
    elif query[0] == 7:
        print(bin(n & mask[query[1]]).count("1"))
        
         
    elif query[0] == 8:
        print(mask[query[1]] & n)



Measured memory_bytes: 5632
X,Y,Z,K=map(int,input().split())
A=sorted([int(i) for i in input().split()],reverse=True)
B=sorted([int(i) for i in input().split()],reverse=True)
C=sorted([int(i) for i in input().split()],reverse=True)
bi_deli=[]
for i in range(min(X,K)):
    for j in range(min(Y,K)):
        if (i+1)*(j+1)>K:
            break
        bi_deli.append(A[i]+B[j])
bi_deli.sort(reverse=True)
tri_deli=[]
for k in range(min(len(bi_deli),K)):
    for l in range(min(Z,K)):
        if (k+1)*(l+1)>K:
            break
        tri_deli.append(bi_deli[k]+C[l])
tri_deli.sort(reverse=True)

print(*tri_deli[:K],sep='\n')

Measured memory_bytes: 5364
#include <iostream>
#include <utility>
#define inf 100000000000000000
#define llint long long

using namespace std;
typedef pair<llint, llint> P;

P seg[1 << 19];

void init()
{
	for(int i = 0; i < (1<<19); i++) seg[i] = make_pair(inf, inf);
}

P query(llint a, llint b, llint k, llint l, llint r)
{
	if(r < a || b < l) return make_pair(inf, inf);
	if(a <= l && r <= b) return seg[k];
	P ret = query(a, b, k*2, l, (l+r)/2);
	ret = min(ret, query(a, b, k*2+1, (l+r)/2+1, r));
	return ret;
}

void update(llint k, P val)
{
	k += (1<<18);
	seg[k] = val;
	while(k > 0){
		k /= 2;
		seg[k] = min(seg[k*2], seg[k*2+1]);
	}
}

llint N;
llint a[200005];

llint calc(llint l, llint r)
{
	if(l > r) return 0;
	
	llint ret = 0;
	P p = query(l, r, 1, 0, (1<<18)-1);
	ret += (p.second - l + 1) * (r - p.second + 1) * p.first;
	ret += calc(l, p.second-1);
	ret += calc(p.second + 1, r);
	return ret;
}

int main(void)
{
	cin >> N;
	for(int i = 0; i < N; i++) cin >> a[i];
	for(int i = 0; i < N; i++) update(i, make_pair(a[i], i));
	
	cout << calc(0, N-1) << endl;
	return 0;
}

Measured memory_bytes: 15232
n, m = map(int, input().split())
A = list(map(int, input().split()))

L = [[0, 0] for i in range(m)]

for i in range(m):
    b, c = map(int, input().split())
    L[i][0] = c
    L[i][1] = b
L.sort(reverse=True)

cnt = 0
for i in range(m):
    c, b = L[i]
    A += [c]*b
    cnt += b
    if cnt >= n:
        break

A.sort(reverse=True)
A = A[0:n]

print(sum(A))



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

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

    int ans = 0;
    for(int i=1; i<=n; i++){
        ans += i;
    }
    cout << ans << endl;

    return 0;
}


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

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repr(i, n) for(int i = (n-1); i >= 0; --i)

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; }

typedef long long ll;
typedef pair<int, int> P;

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

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

    vector<P> v(N);
    map<int, map<int, int>> mp;
    rep(i, N) {
        int y, x;
        cin >> y >> x;
        y--, x--;
        v[i] = P(y, x);
        mp[y][x] = i;
    }

    set<P> y;
    auto f = [](const P &lhs, const P &rhs) { return lhs.second < rhs.second; };
    std::set<P, std::function<bool (const P&, const P&)>> x(f);
    for (auto &p : v) {
        y.emplace(p), x.emplace(p);
    }

    dsu d(N);
    auto xitr = x.rbegin();
    P maxY = P(0, 0);
    for (auto &p : y) {
        int yy = p.first, yx = p.second;

        if (p.first < maxY.first) {
            d.merge(mp[yy][yx], mp[maxY.first][maxY.second]);
        }

        while (p.second < xitr->second) {
            int xy = xitr->first, xx = xitr->second;
            if (p.first < xitr->first) {
                d.merge(mp[yy][yx], mp[xy][xx]);
            }
            if (maxY.first < xitr->first) {
                maxY = *xitr;
            }
            xitr++;
        }
    }

    rep(i, N) {
        cout << d.size(i) << endl;
    }
}

Measured memory_bytes: 52348
#include<iostream>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= end; --i)
#define arep(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll ans = (N - 1) * N / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;

int main(){
  char a,b,c,d;
  cin >> a >>b >>c>>d;

  if(a==b||b==c||c==d) cout << "Bad"<<endl;
  else cout <<"Good"<<endl;

  return 0;
}

Measured memory_bytes: 256
X = int(input())
if(X % 7 == 0):
    print("thu")
elif(X % 7 == 1):
    print("fri")
elif(X % 7 == 2):
    print("sat")
elif(X % 7 == 3):
    print("sun")
elif(X % 7 == 4):
    print("mon")
elif(X % 7 == 5):
    print("tue")
elif(X % 7 == 6):
    print("wed")


Measured memory_bytes: 5592
/* Author: Dhruv Rastogi */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define all(sdk) sdk.begin(),sdk.end()
#define mll map<int, int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;++i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define mp make_pair
#define hell 1000000007
#define endl '\n'
#define vvll vector<vector<int> >
#define vll vector<int>
#define mint map<int,int> 
#define sz(x) (int)x.size()
#define sll set<int>
#define pll pair<int,int>
#define F first
#define S second
const long double PI = acos(-1.0);

void solve(){  
	int lim=1e18;
  	int ans=1;
  	int n;
  	cin>>n;
  	int a[n+1];
  	rep(i,1,n+1){
  		cin>>a[i];
  		if(a[i]==0){
  			cout<<0<<endl;
  			return;
  		}
  	}
  	rep(i,1,n+1){
  		if(lim/ans<a[i]){
  			cout<<-1<<endl;
  			return;
  		}
  		ans*=a[i];
  	}
  	cout<<ans<<endl;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 4420
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int N,i,k;
    int a[1004];
    cin>>N;
    for(i=0;i<N;i++)
    {
        cin>>a[i];
    }
    sort(a,a+N);
    k=a[N-1]-a[0];
    cout<<k<<endl;
    return 0;
}


Measured memory_bytes: 256
import math
a, b, C = map(int, raw_input().split())
S = (a * b * math.sin(math.radians(C))) / 2
c = math.sqrt(a*a + b*b - 2*a*b*math.cos(math.radians(C)))
L = a + b + c
h = (S * 2) / a
print("%f" % (S, ))
print("%f" % (L, ))
print("%f" % (h, ))

Measured memory_bytes: 4436
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}
#define forN(i,n) for(i=0;i<n;i++)
#define forR(i,s,n) for(i=s;i<n;i++)
#define ll long long
#define pb(t,d,n) {t p;int i;forN(i,n){cin>>p;d.push_back(p);}}

using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;

typedef vector<pair<int,int>> vpii;
typedef pair<int,int> pr;

bool cmp(pr left, pr right){
    return left.second<right.second;
}

int main(){
    int i,tmp,res;
    int n;
    vpii a;
    cin >> n;
    forN(i,n){
        cin >> tmp;
        a.push_back({i,tmp});
    }
    sort(a.begin(), a.end(), cmp);
    forN(i,n){
        cout << a[i].first +1 << ' ';
    }
    cout << endl;
}

Measured memory_bytes: 1780
#include <bits/stdc++.h>
 
using namespace std;
 
#define repr(i,a,b) for (int i=a; i<b; i++)
#define rep(i,n) for (int i=0; i<  n; i++)
 
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
 
const long long INF = 1LL << 60;
#define PI 3.14159265359 
 
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
    vector.erase(vector.begin() + index);
}
 
int gcd(int a, int b){
    if(b == 0) return a;
    else return gcd(b, a%b);
}
 
long long lcm (int a, int b){
    return  (long long) a*b /gcd(a,b);
}



int main(){
    int A,B;
    cin >> A >> B;

    if(A >= 6 && A<=12 )cout << B/2 << endl;
    else if (A <= 5) cout << 0 << endl;
    else cout << B << endl;
}


Measured memory_bytes: 3616
use proconio::input;
use proconio::marker::Chars;
use std::cmp::{max, min};
const alpha: [char; 26] = [
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's',
    't', 'u', 'v', 'w', 'x', 'y', 'z',
];

const Alpha: [char; 26] = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S',
    'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
];
fn main() {
    input!(n: usize);
    let table = make_table(n);
    let mut ans = 0;
    for k in 1..=n {
        ans += k * table[k];
    }

    println!("{}", ans);
}

fn make_table(n: usize) -> Vec<usize> {
    let mut table = vec![1; n + 1];
    for i in 2..=n {
        let mut j = i;
        while j <= n {
            table[j] += 1;
            j += i;
        }
    }
    table
}


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

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

int main() {

    int h, w;

    for ( ;; ) {

        std::cin >> h >> w;

        if ( h == 0 && w == 0 ) break;

        REP(i, h) {
            REP(j, w) std::cout << "#";
            std::cout << std::endl;
        }

        std::cout << std::endl;

    }

    return 0;

}



Measured memory_bytes: 3056
//
//  main.cpp
//  C - Go to School
//
//  Created by Hashizo on 2019/09/28.
//  Copyright © 2019 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

int main(int argc, const char * argv[]) {
    string ans = "Yes";


	ll n;
	cin >> n;

	vector<ll> count(n);
	vector<ll> num(n);

	REP(i, n) {
		cin >> count[i];
	}

	REP(i, n) {
		num[count[i]-1] = (i+1);
	}
	
	
	
	REP(i, n) {
			cout << num[i] << " ";
	}
	
	cout << endl;
    return 0;
}


Measured memory_bytes: 2432
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define reps(i, f, n) for (ll i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;
ll const MAX_N = 510000;
ll const MOD = 1000000007;

int main() {
    ll N, M;
    cin >> N >> M;

    ll ans = min(N, M / 2);
    ans += max(0LL, (M - 2 * ans) / 4);

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int n,m,k,sx,sy;
int head,tail;
int D[810][810],Q[1010000][2];
char p[810][810];
void Ins(int x,int y,int d)
{
	if(D[x][y]<=d||p[x][y]!='.')
	{
		return;
	}
	D[x][y]=d;
	++tail;
	Q[tail][0]=x;
	Q[tail][1]=y;
}
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",p[i]+1);
		for(int j=1;j<=m;j++)
		{
			if(p[i][j]=='S')
			{
				sx=i;
				sy=j;
				p[i][j]='.';
			}
			D[i][j]=1e9;
		}
	}
	Ins(sx,sy,0);
	while(head<tail)
	{
		++head;
		int x=Q[head][0];
		int y=Q[head][1];
		Ins(x-1,y,D[x][y]+1);
		Ins(x+1,y,D[x][y]+1);
		Ins(x,y-1,D[x][y]+1);
		Ins(x,y+1,D[x][y]+1);
	}
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=1;j<=m;j++)
//		{
//			printf("%d ",D[i][j]);
//		}
//		printf("\n");
//	}
	int ans=1e9;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(D[i][j]<=k)
			{
				ans=min(ans,1+(min(min(i-1,n-i),min(j-1,m-j))+k-1)/k);
			}
		}
	}
	printf("%d",ans);
	return 0;
}

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

int main()
{
  char c;
  cin>>c;
  
  if(('a' == c)||
     ('e' == c)||
     ('i' == c)||
     ('o' == c)||
     ('u' == c))
  {
    cout<<"vowel"<<endl;
  }
  else
  {
    cout<<"consonant"<<endl;
  }
  
  return 0;
}

    

Measured memory_bytes: 3596
import sys
stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, a, b = na()
ans = 0
if n == 10**4:
        if a == 1:
                ans += 10**4
for x in range(10):
        for y in range(10):
                for z in range(10):
                        for w in range(10):
                                num = x * 1000 + y * 100 + z * 10 + w
                                s = x + y + z + w
                                if (num <= n) and (a <= s) and (b >= s):
                                        ans += num
print(ans)


Measured memory_bytes: 3064
#include<stdio.h>

int main(void)
{
	char n[4];
	int i;
	
	scanf("%s", n);

	for(i=0;i<3;++i){

	if(n[i]=='1'){
	n[i]='9';}
	else if(n[i]=='9'){
	n[i]='1';
	}}
	
	printf("%s",n);
	return 0;
}


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

#define int long long

const int MAX_N = 100000;

struct Data
{
	int v, cost;
	Data() {}
	Data(int _v, int _cost)
	{
		v = _v; cost = _cost;
	}
	bool operator < (const Data &d) const
	{
		return cost > d.cost;
	}
};

int N, M, X, H[MAX_N];
vector<Data> e[MAX_N];

signed main()
{
	cin >> N >> M >> X;
	for (int i = 0; i < N; i++)
	{
		cin >> H[i];
	}
	for (int i = 0; i < M; i++)
	{
		int a, b, t;
		cin >> a >> b >> t;
		a--; b--;
		e[a].push_back(Data(b, t));
		e[b].push_back(Data(a, t));
	}
	
	priority_queue<Data> pq;
	pq.push(Data(0, 0));
	bool isUsed[MAX_N] = {};
	while (!pq.empty())
	{
		Data t = pq.top(); pq.pop();
		if (t.v == N - 1)
		{
			printf("%lld\n", t.cost + (0ll, t.cost + H[N - 1] - X));
			return 0;
		}
		if (isUsed[t.v]) continue;
		isUsed[t.v] = true;
		//printf("%lld, %lld\n", t.v + 1, t.cost);
		for (int i = 0; i < e[t.v].size(); i++)
		{
			Data &_e = e[t.v][i];
			if (H[t.v] < _e.cost) continue;
			pq.push(Data(_e.v, t.cost + _e.cost + max(0ll, max(0ll, X - t.cost - _e.cost) - H[_e.v])));
		}
	}
	puts("-1");
	return 0;
}

Measured memory_bytes: 29804
#include <iostream> //cout
#include <vector> //vector
#include <set> //set
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)


int main() {
    int N, M, Q;
    cin >> N >> M >> Q;

    vector<int> ai(Q);
    vector<int> bi(Q);
    vector<int> ci(Q);
    vector<int> di(Q);

    vector<vector<int> > A_list;
    vector<int> A(N, 1);

    int break_flag = 0;
    while(true){
        // for(int idx = 0; idx < N; idx++){
        //     cout << A.at(idx) << ",";
        // }
        // cout << endl;
        A_list.push_back(A);

        //update A
        A.at(N - 1)++;
        for(int j = N - 1; j >= 0; j--){
            if(A.at(j) > M){
                if(j <= 0){
                    break_flag = 1;
                    break;
                }
                else{
                    A.at(j - 1)++;
                    for(int k = j; k < N; k++){
                        A.at(k) = A.at(j - 1);
                    }
                    continue;
                }
            }
        }

        if(break_flag == 1){
            break;
        }
    }
    
    for(int i = 0; i < Q; i++){
        cin >> ai.at(i) >> bi.at(i) >> ci.at(i) >> di.at(i);
    }

    int max = 0;
    for(int j = 0; j < (int)A_list.size(); j++){
        int sum = 0;
        for(int i = 0; i < Q; i++){
            if(A_list.at(j).at(bi.at(i) - 1) -  A_list.at(j).at(ai.at(i) - 1) == ci.at(i)){
                sum += di.at(i);
            }
        }
        if(sum > max){
            max = sum;
        }
    }
    cout << max << endl;
}


Measured memory_bytes: 9780
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
ll INF = 1000000000000000001; //10^18+1
ll MOD = 1000000007; //10^9+7
//cout << fixed << setprecision(15); (小数点以下表示)


int main() {
  ll N,mi,cnt=1;
  cin >> N;
  ll P[N];
  for(int i=0;i<N;i++){
    cin >> P[i];
  }
  mi=P[0];
  for(int i=1;i<N;i++){
    if(P[i]<mi){
      cnt++;
      mi=P[i];
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;typedef vector<ll> vll;
#define fill(a) memset(a, 0, sizeof (a))
#define all(v) (v).begin(),(v).end()
#define sp(k) cout<<setprecision(k)<<fixed;
#define rep(i,a) for(int i=0; i<a;i++)
#define rep1(i,a,b) for(int i=(a);i<=(b);++i)
#define irep(i,b,a) for(int i=(b);i>=(a);--i)
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define unq(v) sort(all(v)),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define getpos(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define _ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define sqr(a) ((a)*(a))
#define sz(a) int(a.size())
#define ff first
#define ss second
#define pb push_back

const int INF = 1e9 + 10;
const double pi = acos(-1.0);
const int mod = 1000000007; // (int)1e9+7
const int maxn = 2000100;

int main(){
        _ios;

            string s;
	cin >> s;
	if (s[0] == s[1] && s[1] == s[2]) {
		cout << "No" << endl;
	} else {
		cout << "Yes" << endl;
	}
	return 0;
return 0;
}







Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)

# +-+-
ret1 = 0
sum = 0
n.times do |i|
  sum += a[i]
  if i.even? && sum <= 0 then
    ret1 += (sum.abs + 1)
    sum = 1
  elsif i.odd? && sum >= 0 then
    ret1 += (sum.abs + 1)
    sum = -1
  end
end

#-+-+
ret2 = 0
sum = 0
n.times do |i|
  sum += a[i]
  if i.even? && sum >= 0 then
    ret2 += (sum.abs + 1)
    sum = -1
  elsif i.odd? && sum <= 0 then
    ret2 += (sum.abs + 1)
    sum = 1
  end
end
puts [ret1, ret2].min

Measured memory_bytes: 11404
local mce, mfl, msq, mmi, mma = math.ceil, math.floor, math.sqrt, math.min, math.max

local primes = {}
local allnums = {}
local a = 100000
allnums[1] = 0
for i = 2, a do allnums[i] = 1 end
for i = 2, a do
  if(allnums[i] == 1) then
    table.insert(primes, i)
    local lim = math.floor(a / i)
    for j = 2, lim do
      allnums[j * i] = 0
    end
  end
end
local map = {}
map[1] = 0
map[2] = 0
for i = 3, a do
  if(i % 2 == 1 and allnums[i] == 1 and allnums[mfl((i + 1) / 2)] == 1) then
    map[i] = map[i - 1] + 1
  else
    map[i] = map[i - 1]
  end
end
local q = io.read("*n")
for i = 1, q do
  local l, r = io.read("*n", "*n")
  if(l == 1) then print(map[r])
  else print(map[r] - map[l - 1]) end
end


Measured memory_bytes: 2944
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), true);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.flush();
		out.close();
	}
}

class Pair<A, B> {
	A first;
	B second;

	Pair(A first, B second) {
		this.first = first;
		this.second = second;
	}

}

class TaskB {
	long INF = (long) 1e18 + 5;
	long mod = (long) 1e9 + 7;

	public void solve(int testNumber, InputReader in, PrintWriter pw) {
		int n = in.nextInt();
		int k = in.nextInt();
		int arr[] = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = in.nextInt();
		}
		Arrays.sort(arr);
		int min = Integer.MAX_VALUE;
		for (int i = 0; i + k - 1 < n; i++) {
			min = Math.min(Math.abs(arr[i + k - 1] - arr[i]), min);
		}
		pw.println(min);
	}

	long fib(int N) {
		long fib[] = new long[N + 1];
		fib[0] = 1;
		fib[1] = 1;
		for (int i = 2; i <= N; i++) {
			fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
		}
		return fib[N] % mod;
	}

	long sum(int i, int j, long arr[]) {
		long sum = 0;
		for (int k = i; k <= j; k++) {
			sum += arr[k];
		}
		return sum;
	}

	boolean FirstRow_Col(Pair<Integer, Integer> pair) {
		return pair.first == 0 || pair.second == 0;
	}

	int __gcd(int a, int b) {
		if (b == 0)
			return a;
		return __gcd(b, a % b);

	}

	public int getInt(int num) {
		int ret = -1;
		switch (num) {
		case 0:
			ret = 6;
			break;
		case 1:
			ret = 2;
			break;
		case 2:
			ret = 5;
			break;
		case 3:
			ret = 5;
			break;
		case 4:
			ret = 4;
			break;
		case 5:
			ret = 5;
			break;
		case 6:
			ret = 6;
			break;
		case 7:
			ret = 3;
			break;
		case 8:
			ret = 7;
			break;
		case 9:
			ret = 6;
			break;
		}
		return ret;
	}

	public int isPow(long num) {
		int count = 0;
		while (num > 0) {
			num /= 2;
			count++;
		}
		return count;
	}
}

class InputReader {
	BufferedReader br;
	StringTokenizer st;

	public InputReader(InputStream in) {
		br = new BufferedReader(new InputStreamReader(in));
		st = null;
	}

	public String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


Measured memory_bytes: 41036
class UnionFind():
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def Union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        if self.find(x) == self.find(y):
            return True
        else:
            return False
n,m = map(int,input().split())
bridge = []
for i in range(m):
    s,t = map(lambda x:int(x) - 1,input().split())
    bridge.append([s,t])
cnt = 0
# 取り除く辺を考える
for i in range(m):
    Uni = UnionFind(n)
    for j,root in enumerate(bridge,start = 0):
        if i == j: # 一緒のところをのぞいている
            continue
        s,t = root
        Uni.Union(s,t)
    # ここで、そのiのところ(除いてるところ)を調べる
    s,t = bridge[i]
    # 親が一緒なら、別にそこは橋じゃない それが無くても行けるから
    if not Uni.same(s,t):
        cnt += 1
print(cnt)


Measured memory_bytes: 3064
def sakuzyo(i):
    if koteirow[i] == 1:
        sakuzyo(i-1)
    else:
        for j in range(N):
            if haiti[i][j] == 'Q':
                #print('delete {} {}'.format(i, j))
                haiti[i][j] = '.'
                row[i] = 0
                col[j] = 0
                dpos[i + j] = 0
                dneg[i - j + (N - 1)] = 0
                if j == N-1:
                    sakuzyo(i-1)
                else:
                    sounyuu(i, j+1)


def sounyuu(i, j):
    if koteirow[i] == 0:
        for k in range(j, N):
            flag = 0
            if col[k] == 0 and dpos[i+k] == 0 and dneg[i-k+(N-1)] == 0:
                haiti[i][k] = 'Q'
                #print('add {} {}'.format(i, k))
                row[i] = 1
                col[k] = 1
                dpos[i+k] = 1
                dneg[i-k+(N-1)] = 1
                flag = 1
                if i == N-1:
                    for o in range(N):
                        for p in range(N):
                            print(haiti[o][p], end='')
                        print()
                    exit()
                else:
                    sounyuu(i+1, 0)
        if flag == 0:
            sakuzyo(i-1)
    elif i == N-1:
        for o in range(N):
            for p in range(N):
                print(haiti[o][p], end='')
            print()
        exit()
    else:
        sounyuu(i+1, j)


k = int(input())
data = [list(map(int, input().split()))for _ in range(k)]

N = 8
row = [0]*N
col = [0]*N
dpos = [0]*(N*2-1)
dneg = [0]*(N*2-1)
haiti = [['.']*N for _ in range(N)]
koteirow = [0]*N

for i in data:
    haiti[i[0]][i[1]] = 'Q'
    row[i[0]] = 1
    col[i[1]] = 1
    dpos[i[0]+i[1]] = 1
    dneg[i[0] - i[1] + (N - 1)] = 1
    koteirow[i[0]] = 1

sounyuu(0, 0)




Measured memory_bytes: 5644
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K = sc.nextInt(), X = sc.nextInt(), Y = sc.nextInt();
		if (K >= N)
			System.out.println(X * N);
		else
			System.out.println(K * X + (N - K) * Y);
	}

}


Measured memory_bytes: 9556
#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

vector<pair<ll, ll>> primeFactorization(ll n) {
    vector<pair<ll, ll>> result;
    for (ll i = 2; i * i <= n; i++) {
        ll num = 0;
        while (n % i == 0) {
            n /= i;
            num++;
        }
        if (num != 0) {
            result.push_back({ i, num });
        }
    }

    if (n != 1) {
        result.push_back({ n, 1 });
    }

    return result;
}

int main() {
    ll N;
    cin >> N;

    set<ll> st;
    st.insert(1);
    for (const auto& p : primeFactorization(N)) {
        set<ll> next;
        for (ll e : st) {
            for (ll j = 0; j <= p.second; j++) {
                next.insert(e * pow(p.first, j));
            }
        }
        st = next;
    }

    ll ans = 0;
    for (ll e : st) {
        ll m = N / e - 1;
        if (m > e) {
            ans += m;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
    static void Main(string[] args){
    var vals = Console.ReadLine().Split().Select(x => double.Parse(x)).ToList();
    var N=vals[0];
    var D=vals[1];
    double tmp=N/(2*D+1);
    double ans=Math.Ceiling(tmp);
    Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11348
#include<stdio.h>
int main(void)
{
	int r, d, x,i;
	scanf("%d", &r);
	scanf("%d", &d);
	scanf("%d", &x);
	for (i = 0; i < 10; i++) {
		printf("%d\n", r * x - d);
		x = r * x - d;
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<iomanip>

using namespace std;

int main() {
    int M1, D1, M2, D2;
    cin >> M1 >> D1;
    cin >> M2 >> D2;
    if(M1!=M2) {
        cout << 1 << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

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


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()


using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll  = long long;

using point = complex<double>;


void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}


const double EPS = 1e-8;
const long long mod = 1e9+7;

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

const int N = 3e5 + 5;


int n , m;
int arr[200][200];
int x;
int col[10060];
bool vis[205][205];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    cin >> x;
    for(int i = 0; i < x; ++i)
        cin >> col[i];
    int lx , ly;
    lx = 0,ly = 0;
    bool isr = 1;
    for(int i = 0; i < x; ++i){
        for(int j = 0; j < col[i]; ++j){
           arr[lx][ly] = i+1;
           if(isr)ly++;
           else ly--;
           if(ly == m){
                isr = 0;
                ly = m - 1;
                lx++;
           }else if(ly == -1){
                isr = 1;
                ly = 0;
                lx++;
           }

        }
    }
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cout << arr[i][j] << " \n"[j == m - 1];
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <string.h>

int main(void){
	char str[200001] = {};
	int i, j, len;
	
	gets(str);
	
	len = strlen(str);
	
	for (i = 0; i < len; i++){
		if (str[i] =='A'){
			break;
		}
	}
	
	for (j = len-1; j > i; j--){
		if (str[j] =='Z'){
			break;
		}
	}
	
	printf("%d\n", j-i+1);
	
	return 0;
}

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

typedef long long ll;
#define PI 3.1415926535897932384626433
#define mod 1000000007

int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

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

int main(){
    ll l, r;
    cin >> l >> r;
    ll m = 2e10;
    for (ll i = l; i <= r; i++){
        for (ll j = l; j <= r; j++){
            if(i < j){
                m = min(m, (i * j) % 2019);
            }
            if(m == 0){
                cout << 0 << endl;
                return 0;
            }
        }
    }
    cout << m << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N;
  set<string> s;
  cin>>N;
  string S;
  for(int i = 0;i < N;i++){
    cin>>S;
    s.insert(S);
  }
  cout<<s.size()<<'\n';
}

Measured memory_bytes: 19168