akhauriyash/Code-Regression huggingface dataset:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    s = s_input()

    al=[chr(ord('a') + i) for i in range(26)]

    if s in al:
        print('a')
    else:
        print('A')

if __name__ == '__main__':
    main()


Measured memory_bytes: 72704
/*
    ThunderClap and Flash.
    Raunaq Singh
*/
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
#define ThunderClap ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define debugg(something)   cout<<#something<<" - "<<something<<"\n";
#define vi vector
#define umap unordered_map
#define uset unordered_set
#define mset multiset
#define LB lower_bound
#define UB upper_bound
#define mp make_pair
#define pb push_back
#define in insert
#define s second                                                                                                                                                                                                                                                                                                                
#define f first
#define maxElement *max_element
#define minElement *min_element
#define MAX 100000
#define mod 1000000007
#define inf 1000000000000000000
#define mI2 500000004
inline ll add(ll a, ll b){ return ((a%mod)+(b%mod))%mod;}
inline ll mul(ll a, ll b){ return ((a%mod)*(b%mod))%mod;}
inline ll sub(ll a, ll b){ return ((a%mod)-(b%mod)+mod)%mod;}

void Flash(){
    ll a,b;
    cin>>a>>b;
    cout<<(a*b)/__gcd(a,b);
}

int main(int argc, char const *argv[]){
    ThunderClap;
    ll t=1;
    //cin>>t;
    for(ll i=1;i<=t;i++){
        //cout<<"Case #"<<i<<": ";
        Flash();
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int m1,m2,temp;
  cin>>m1;cin>>m2;
  if(m1>m2){
    temp=m1;
    m1=m2;m2=temp;
  }
  cin >> temp;
  if(m2<temp) cout << m1 + m2;
  else cout << m1 + temp;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;
vint G[111111];
bool vis[111111];
int ord[111111],low[111111];
vint articulation;
vpint bridge;

void dfs(int v,int p,int &k){
    ord[v]=k++;
    low[v]=ord[v];
    vis[v]=true;

    bool flag=false;
    int cnt=0;
    for(auto u:G[v]){
        if(vis[u]){
            if(u!=p)chmin(low[v],ord[u]);
        }
        else{
            cnt++;
            dfs(u,v,k);
            if(ord[v]<low[u])bridge.pb({min(v,u),max(v,u)});
            if(ord[v]<=low[u])flag=true;
            chmin(low[v],low[u]);
        }
    }
    if(p==-1&&cnt<=1)flag=false;
    if(flag)articulation.pb(v);
}

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b;cin>>a>>b;
        G[a].pb(b);G[b].pb(a);
    }
    int k=0;dfs(0,-1,k);
    sort(all(articulation));
    for(auto v:articulation){
        cout<<v<<endl;
    }
}

Measured memory_bytes: 7964
//package atcoderdp;
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class Main {
	static Scanner scn = new Scanner(System.in);
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = scn.nextInt();
		int[] h = new int[n];
		for(int i =0;i<n;i++) {
			h[i] = scn.nextInt();
		}
		
		long ans = find(h,0, new Long[n]);
		System.out.println(ans);
	}
	public static long find(int[] h, int idx, Long[] dp) {
		if(idx==h.length-1) {
			return 0;
		}
		if(dp[idx]!=null) {
			return dp[idx];
		}
		long c1 = Integer.MAX_VALUE;
		long c2 = Integer.MAX_VALUE;
		if(idx+1<h.length) {
			c1 = Math.abs(h[idx]-h[idx+1])+find(h,idx+1,dp);
		}
		if(idx+2<h.length) {
			c2 = Math.abs(h[idx]-h[idx+2])+find(h, idx+2,dp);
		}
		return dp[idx]=Math.min(c1, c2);
	}
}


Measured memory_bytes: 66132
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

class STACK{

public:
	STACK(){
		index = 0;
	}
	void push(int data){
		array[index++] = data;
	}
	int pop(){
		index--;
		return array[index];
	}
	bool isEmpty(){
		return index == 0;
	}
	int getIndex(){
		return index;
	}

private:
	int array[10];
	int index;
};

int main(){
	int w;
	STACK stack;

	while(scanf("%d",&w) != EOF){
		for(int i = 512; i>= 1; i /= 2){
			if(w>=i){
				stack.push(i);
				w -= i;
			}
		}

		while(!stack.isEmpty()){
				if(stack.getIndex() == 1){
					printf("%d\n",stack.pop());
				}else{
					printf("%d ",stack.pop());
				}
		}
	}

	return 0;
}

Measured memory_bytes: 2724
from functools import *
from itertools import *
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
 
M = 10**9+7
N = int(input())

@lru_cache(maxsize=None)
def mod_inv(x):
  return 1 if x == 1 else M // x * -mod_inv(M%x) % M

Weight = [0]*(N+1)
Size = [0]*(N+1)
def calc_subtree(v):
  W, S = 1, 1
  for child in Edge[v]:
    Edge[child].remove(v)
    calc_subtree(child)
    W = W * Weight[child] % M
    S += Size[child]
  Weight[v] = W * S % M
  Size[v] = S

Ans = [0]*(N+1)
def calc_ans(v, a):
  Ans[v] = a
  for child in Edge[v]:
    n = Size[child]
    calc_ans(child, a * n * mod_inv(N-n) % M)

Edge = [set() for i in range(N+1)]
fact = N
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)
  
calc_subtree(1)
calc_ans(1, mod_inv(Weight[1]) * fact % M)

for a in islice(Ans, 1, None):
  print(a)



Measured memory_bytes: 80336
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 ll, rr, dd, ans = 0;
	cin >> ll >> rr >> dd;
	for(int64 ii = ll;ii <= rr;ii++)
	{
		if(ii % dd == 0)
		{
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
int n;
int k;
int ans = 1;
cin >> n >> k;
while(n--)
{
if(ans + k < ans * 2) ans = ans + k;
else ans = ans*2;

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

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
#include <iomanip>
#include<sstream>
#include<string.h>
using namespace std;
int main()
{
	int i, a, b;
	while (cin >> i)
	{
		a = i / 500;
		a *= 1000;
		i %= 500;
		b = i / 5;
		b *= 5;
		a += b;
		cout << a << '\n';
	}
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.ExceptionServices;
using System.Runtime.Intrinsics.X86;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = Read();
            if (S[S.Length - 1] == 's')
            {
                WriteLine($"{S}es");
            }
            else
            {
                WriteLine($"{S}s");
            }
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


Measured memory_bytes: 25880
//I read the news today, oh boy
//About a lucky man who made the grade
 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(x) ll((x).size())
#define all(v) (v).begin(),(v).end()
#define trace(x) cerr << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define For(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
#define roF(i,a,b) for(ll i = ll(a); i >= ll(b); i--)
using namespace std;

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

const ll N=1e6;

vii V;

int main(){
	fastio;
	ll n, k; cin>>n>>k;
	For(i,0,n){
		ll a, b; cin>>a>>b;
		V.pb(mp(a,b));
	}
	sort(all(V));
	ll acum=0;
	int i=-1;
	while(i<n-1 && acum<k){
		i++;
		acum+=V[i].ss;
	}
	cout << V[i].ff << endl;
	return 0;
}



Measured memory_bytes: 2548
function Main(input) {
    var input = input.split('\n');
    var nidan = input[1].split(' ').map(n => parseInt(n, 10)).sort((a, b) => a < b ? -1 : 1);
    console.log(nidan[nidan.length-1] - nidan[0]);

    }
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7372
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int A = scan.nextInt();
        int sub = 0;
        int sub2 = 0;
        int ans = 999999999;

        for(int i=0;i<A;i++){
            int b = scan.nextInt();
            sub += b*b;
            sub2 += b;
        }

        for(int i=1;i<=999999999;i++){
            int p = sub-2*sub2*i+i*i*A;
            if(p<=ans){
                ans = p;
            }else{
                break;
            }
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 21972
n = int(input())
if n == 1:
	print('1')
elif 2 <= n <= 3:
	print('2')
elif 4 <= n <= 7:
	print('4')
elif 8 <= n <= 15:
	print('8')
elif 16 <= n <= 31:
	print('16')
elif 32 <= n <= 63:
	print('32')
else:
	print('64')

Measured memory_bytes: 3060
#include <stdio.h>
int main () {
  int x, y, a, b, n;

  scanf("%d%d", &x, &y);
  if(x >= y) {
    a = x;
    b = y;
  }
  else {
    a = y;
    b = x;
  }

  n = a % b;
  while(n != 0) {
    a = b;
    b = n;
    n = a % b;
  }

  printf("%d\n", b);
  return 0;
}

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

void c_p_c()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

void lcs(string s1, string s2)
{
	int m = s1.length();
	int n = s2.length();

	int dp[m + 1][n + 1] = {};

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (s1[i - 1] == s2[j - 1])
				dp[i][j] = 1 + dp[i - 1][j - 1];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
		}
	}

	//printing lcs
	int index = dp[m][n];
	char ans[index + 1];
	ans[index] = '\0';
	int i = m, j = n;
	while (i > 0 and j > 0)
	{
		if (s1[i - 1] == s2[j - 1])
		{
			ans[index - 1] = s1[i - 1];
			i--;
			j--;
			index--;
		}
		else if (dp[i - 1][j] > dp[i][j - 1])
			i--;
		else
			j--;
	}
	cout << ans << endl;
	return;
}

void solve()
{
	string s1, s2;
	cin >> s1 >> s2;
	lcs(s1, s2);
}

int32_t main()
{
	c_p_c();
	solve();
	return 0;
}

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

int main (){
    long long int n;
    cin >> n;
    long long int c=0;
    if(n%2==1);
    else{
        while(n%10!=0)
            n-=2;
            n/=2;
            long long int g = 5;
            while(n>=g){
            c+=n/g;
            n/=g;
        }
    }
    cout << c << "\n";
    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define rep2(i, a)for(auto i : a)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x, std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll co(ll n, ll k) { ll a = 1; rep(i, 1ll, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

int main(void) {
	int k, ans = 1;
	cin >> k;
	vector<int> f(k);
	ll v = 7 % k;
	while (v) {
		v *= 10;
		v += 7;
		v %= k;
		if (f[v]) {
			puts("-1");
			return 0;
		}
		f[v] = 1;
		ans++;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 7120
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
A = LI()
if all([a > 0 for a in A]):
    now = min(A)
    print(sum(A) - now * 2)
    A.remove(now)
    last = A.pop()
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
    print(last, now)
elif all([a < 0 for a in A]):
    now = max(A)
    print(-sum(A) + now * 2)
    A.remove(now)
    while A:
        nxt = A.pop()
        print(now, nxt)
        now -= nxt
else:
    print(sum([abs(i) for i in A]))
    minus = []
    plus = []
    for a in A:
        if a > 0:
            plus += [a]
        elif a < 0:
            minus += [a]
        else:
            if not plus:
                plus += [a]
            else:
                minus += [a]
    minus_now = minus.pop()
    plus_now = plus.pop()
    while plus:
        nxt = plus.pop()
        print(minus_now, nxt)
        minus_now -= nxt
    print(plus_now, minus_now)
    plus_now -= minus_now
    while minus:
        nxt = minus.pop()
        print(plus_now, nxt)
        plus_now -= nxt


Measured memory_bytes: 61808
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();
		char[] S = new char[N];
		S = sc.next().toCharArray();

		S[K-1] = S[K-1]=='A' ? 'a' : S[K-1]=='B' ? 'b' : 'c';

		System.out.println(S);

	}


}

Measured memory_bytes: 22484
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    A,B,C = list(map(int,_in[0].split(' ')))  # type:list(int)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    if [A%2,B%2,C%2] in [[0,0,0],[1,1,1]]:
        pass
    else:
        if [A%2,B%2,C%2] in [[0,1,1],[1,0,0]]:
            B+=1
            C+=1
        elif [A%2,B%2,C%2] in [[1,0,1],[0,1,0]]:
            A+=1
            C+=1
        elif [A%2,B%2,C%2] in [[1,1,0],[0,0,1]]:
            A+=1
            B+=1
        cnt += 1
    arr = sorted([A,B,C])
    cnt += abs(arr[2]-arr[0])//2
    cnt += abs(arr[2]-arr[1])//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


Measured memory_bytes: 38384
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

mod = 10**9+7 #出力の制限
N = 10**5
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % 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 )
# a = cmb(n,r)

mod = 10**9+7 #出力の制限
N = 10**5
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % 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 )
# a = cmb(n,r)



n = onem()

co = 0

po = n // 3

for i in range(0,po):
    co += cmb(n-2*(i+1)-1,i)
    co %= mod
    
print(co)






Measured memory_bytes: 105704
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <map>

int main(){

    int A1, A2, A3;
    scanf("%d",&A1);
    scanf("%d",&A2);
    scanf("%d",&A3);
    if (A1+A2+A3>21){
        printf("bust\n");
    } else {
        printf("win\n");
    }
    return 0;
}

Measured memory_bytes: 256
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <iomanip>
#include <tuple>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;

string table[22];
int w,h;
int dist[11][20][20];
int xs[11];
int ys[11];
int cost[11][1<<11];
void exec()
{
	cin >> w >> h;
	if(w==0&&h==0)exit(0);
	int c=1;
	for(int i=0;i<h;i++){
		cin >> table[i];
		for(int j=0;j<w;j++){
			switch(table[i][j]){
				case '*':
					xs[c]=i;
					ys[c]=j;
					c++;
					break;
				case 'o':
					xs[0]=i;
					ys[0]=j;
					break;
			}
		}
	}
	fill(dist[0][0],dist[0][0]+11*20*20,10000);
	for(int p=0;p<c;p++){
		auto ds=dist[p];
		ds[xs[p]][ys[p]]=0;
		queue<P> q;
		q.push(P(xs[p],ys[p]));
		while(q.size()){
			int x=q.front().first;
			int y=q.front().second;
			q.pop();
			int d=ds[x][y]+1;
			int dx[]={0,-1,0,1};
			int dy[]={-1,0,1,0};
			for(int i=0;i<4;i++){
				int xx=x+dx[i];
				int yy=y+dy[i];
				if(0<=xx&&xx<h&&0<=yy&&yy<w&&
				  table[xx][yy]!='x'&&
				  ds[xx][yy]>d){
					ds[xx][yy]=d;
					q.push(P(xx,yy));
				}
			}
		}
	}
	fill(cost[0],cost[0]+11*(1<<11),10000);
	cost[0][1]=0;
	for(int i=1;i<(1<<c);i+=2){
		for(int j=0;j<c;j++){
			for(int k=0;k<c;k++){
				int t=cost[k][i]+dist[k][xs[j]][ys[j]];
				cost[j][i|(1<<j)]=min(cost[j][i|(1<<j)],t);
			}
		}
	}
	int ret=10000;
	for(int i=0;i<c;i++){
		ret=min(ret,cost[i][(1<<c)-1]);
	}
	if(ret==10000)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << ret << endl;
	}
}
int main() {
	while(1)exec();
}

Measured memory_bytes: 1328
#include <stdio.h>

int main(){
    int a,b,c,d=0;
  	int R=0,G=0,B=0,N=0,P=0;
    scanf("%d %d %d %d",&R,&G,&B,&N);
  	a=N/R;
  	b=N/G;
  	c=N/B;
  	for(int i=0;i<=a;i++)
    {
      for(int j=0;j<=b;j++)
      {
        if(R*i+G*j==N)d++;
        else{
        	P=N-(R*i+G*j);
        	if(P>=B&&P%B==0)d++;
        }
      }
    }
  	printf("%d",d);
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))//0或-1
#define fs first
#define sc second
#define mp make_pair
#define L(x) (1<<x)
#define next Next
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=1e2+10;
const int maxm=1e3+10;
const int mod=1e9+7;
int H,W,n;
int a[maxn*maxn];
int ans[maxn][maxn];
int main()
{
   // freopen("in.txt","r",stdin);
    while(~scanf("%d %d",&H,&W))
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        int k=1;
        for(int i=1;i<=H;i++)
        {
            for(int j=(i%2==1?1:W);j>=1&&j<=W;j+=(i%2==1?1:-1))
            {
                ans[i][j]=k;
                a[k]--;
                if(a[k]==0) k++;
            }
        }
        for(int i=1;i<=H;i++)
            for(int j=1;j<=W;j++)
            printf("%d%s",ans[i][j],j==W?"\n":" ");
    }
    return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;
long long gcd(long long c, long long d);

int main() {
  long long a,b,c,d,total;
  cin >> a >> b >> c >> d;
  long long e = (c*d)/gcd(c,d);
  //cout << e << endl;
  //cout <<  b/c << b/d << (a-1)/c << (a-1)/d << b/e << (a-1)/e << endl;

  total = b/c - (a-1)/c + b/d - (a-1)/d;
  total -= (b/e - (a-1)/e);
  cout << b - a - total +1 << endl;

}

long long gcd(long long c, long long d){
    long long mx = max(c,d);
    long long mi = min(c,d);
    long long tmp=0;
    while(mi > 0){
        tmp = mx % mi;
        if(tmp==0){
            return mi;
        } else{
            mx = mi;
            mi = tmp;
        }
    }
    return 1;
} 


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

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

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }
	mint operator-()const{ return mint(-x); }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

mint operator+(long long x,const mint& m){ return mint(x)+m; }
mint operator-(long long x,const mint& m){ return mint(x)-m; }
mint operator*(long long x,const mint& m){ return mint(x)*m; }
mint operator/(long long x,const mint& m){ return mint(x)/m; }

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

	int hist[128]={};
	rep(i,n) hist[s[i]]++;

	mint ans=1;
	for(int c='a';c<='z';c++) ans*=hist[c]+1;
	cout<<ans-1<<'\n';

	return 0;
}


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

long long x,y,ans;

int main(){
    cin >> x >> y;

    ans = abs(abs(y) - abs(x));

    if(abs(x)<abs(y)){
        if(x>=0 && y>0) ;
        else if(y==0) ;
        else if(x<0 && y>0) ans++;
        else if(x>=0 && y<0) ans++;
        else ans+=2;
    }
    else{
        if(x>0 && y>0) ans+=2;
        if(x>0 && y==0)ans++;
        else if(x<0 && y==0);
        else if(x<0 && y>0) ans++;
        else if(x>0 && y<0) ans++;
        else ;
    }

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


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl
#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define gap cout<<endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) ll((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    fo(i,n) cin>>a[i];
    int avg=accumulate(all(a),0)/n;
    vector<int> nn{avg,avg+1};
    
    int maax=INT_MAX;
    for(auto j:nn){
        int tmp=0;
        fo(i,n){
            tmp=tmp+(a[i]-j)*(a[i]-j);
            
            
        }
        maax=min(maax,tmp);
    }
    cout<<maax<<endl;
    
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();

		if(a < b && b < c){
			System.out.printf("Yes\n");
		}else{
			System.out.printf("No\n");
		}
	}
}





Measured memory_bytes: 26416
#include <iostream>

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

  long long int power = 1;
  for (int i = 1; i <= N; ++i) {
    power = i * power % (1000000000 + 7);
  }
  std::cout << power << std::endl;

  return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vl a(n), b(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i] >> b[i];
    }
    ll ret = 0;
    for (int i = 0; i < n; ++i) {
        bool ok = true;
        for (int j = 0; j <= 30; ++j) {
            if (!((1LL << j) & k) && ((1LL << j) & a[i])) {
                ok = false;
                break;
            }
        }
        if (ok)
            ret += b[i];
    }
    for (int i = 0; i <= 30; ++i) {
        if (!(1LL << i & k))
            continue;
        ll temp = 0;
        ll tempk = k;
        tempk -= 1LL << i;
        for (int j = 0; j < i; ++j) {
            if (!(tempk & 1LL << j))
                tempk += 1LL << j;
        }
        for (int l = 0; l < n; ++l) {
            bool ok = true;
            for (int j = 0; j <= 30; ++j) {
                if (!((1 << j) & tempk) && ((1 << j) & a[l])) {
                    ok = false;
                    break;
                }
            }
            if (ok)
                temp += b[l];
        }
        chmax(ret, temp);
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 1792
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
sys.setrecursionlimit(1000000)
# do magic here
n = int(input())
heights = [int(x) for x in input().split()]

MAX = 10000000

dp = {}


def solve(x):
    if x==0:
        return 0
    if x < 0:
        return MAX
    if x in dp:
        return dp[x]
    a = abs(heights[x-1] - heights[x]) + solve(x-1)
    b = abs(heights[x-2] - heights[x]) + solve(x-2)
    dp[x] = min(a,b)
    return dp[x]

print(solve(n-1))


Measured memory_bytes: 106784
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    int c = 0;
    int C = 0;
    for (int i = 2; i < s.size() - 1; ++i)
        if (s[i] == 'C')
            C++;

    for (int i = 0; i < s.size(); ++i)
        if (!isupper(s[i]))
            c++;

    if (c != s.size() - 2 || C != 1 || s.front() != 'A')
        cout << "WA";
    else
        cout << "AC";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define mem(a,b) memset(a,b,sizeof(a))
#define IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int INF=0x3f3f3f3f;
const ll inf=0x3f3f3f3f3f3f3f3f;
const int mod=1e9+7;
const int maxn=1e5+5;
int n,m,q;
int a[55],b[55],c[55],d[55],A[15];
int ans=0;
void dfs(int dep,int pre){
	if(dep==n+1){
		int sum=0;
		for(int i=1;i<=q;i++){
			if(A[b[i]]-A[a[i]]==c[i]) sum+=d[i];
		}
		ans=max(ans,sum);
		return ;		
	}
	for(int i=pre;i<=m;i++){
		A[dep]=i;
		dfs(dep+1,i);
	}
}
int main(){
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
	}
	dfs(1,1);
	cout<<ans<<endl;
}

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

#define INF 1e9
using namespace std;
typedef long long ll;

int main() {

    int a, b, c; cin >> a >> b >> c;

    if (a == b + c || b == c + a || c == a + b) {
        puts("Yes");
    } else {
        puts("No");
    }
}

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

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() {
    int N; cin >> N;
    vector<long long> s(N);
    for (int i = 0; i < N; ++i) cin >> s[i];

    long long res = 0;
    for (int p = 1; p <= N-1; ++p) {
        if ((N-1) % p == 0) {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < j; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
        else {
            long long tmp = 0;
            long long cur = 0;
            int i = 0, j = N-1;
            for (; i < N-1 && j > p; i += p, j -= p) {
                cur += s[i] + s[j];
                chmax(tmp, cur);
            }
            chmax(res, tmp);
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 1024
import math

def get_float():
    while True:
        try:
            yield float(raw_input())
        except EOFError:
            break
        
v_lis = list(get_float())

for v in v_lis:
    t = v / 9.8
    y = 4.9 * (t**2)
    _N = (y + 5) / 5
    N = int(math.ceil(_N))
    print N

Measured memory_bytes: 4376
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<stdlib.h>

int main(){
	int *R,i,n,pr,vMin=0;
	
	scanf("%d", &n);
	R = (int *)malloc(sizeof(int)*n);

	
	for (i = n; i >0; --i) 	scanf("%d", R + n-i);
	vMin = R[0];
	pr =R[1]-R[0];
	for (i = 1; i < n; i++) {
		if (R[i] - vMin > pr) pr = *(R + i) - vMin;
		if (R[i] < vMin)vMin = *(R + i);
	}
	printf("%d\n", pr);
	return 0;
}

Measured memory_bytes: 1380
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;
    static final int ALF = 26;

    Main() {
        Scanner sc = new Scanner(System.in);
        long ans = 0;
        int N = sc.nextInt();
        int[] A = new int[N];
        boolean fullEven = true;
        for(int i=0;i<N;i++){
            A[i]=sc.nextInt();
            fullEven &= A[i]%2==0;
        }
        System.out.println(fullEven?"second":"first");
    }

    public static void main(String[] args) {
        new Main();
    }
}


Measured memory_bytes: 59428
#include<iostream>
#include<string>
using namespace std;
int main()
{
    int Z=0;
    //-----------

    string strs[50];
    int n;

    int tmpcount[26]={0};
    int count[26]={0};
    int init = 0;

    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>strs[i];
    }

    //文字列のなかで最小の文字が含まれる文字列の文字数を探す（意味不明）



    for(int i=0;i<n;i++)
    {
        //文字の全探索
        for(int j=0;j<strs[i].size();j++)
        {
            //デバッグ
            //cout<< (int)strs[i][j]-97 <<"=";
            //cout<<strs[i][j]<<endl;

            //文字数をカウント
            tmpcount[(int)strs[i][j]-97] ++;

        }
        //カウントを更新

        if(init == 0){
            for(int j=0;j<26;j++)
            {
                count[j] = tmpcount[j];//初回は全部コピー
            }
            init = 1;
        }
        else 
        {
             for(int j=0;j<26;j++)
            {
                if(count[j]!=tmpcount[j])
                count[j] = min(count[j],tmpcount[j]);//小さい方を代入

            }
        }

        //tmpの初期化
        for(int j=0;j<26;j++)
            {
               
                tmpcount[j] = 0;

            }


    }

    //出力

    for(int i=0;i<26;i++)
    {
        if(count[i]>0)
        {
            for(int j=0;j<count[i];j++)
            {
                cout<<(char)(97+i);
            }
        }
    }

    cout<<endl;

    //------------
    cin>>Z;//何と入力がなければ消さなくてもいいらしい

    return 0;
}

Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */

    int x = sc.nextInt();
    int a = sc.nextInt();

    if (x < a) {
      os.println("0");
    } else {
      os.println("10");
    }

  }
}

Measured memory_bytes: 23764
n=int(input())
p=list(map(int,input().split()))
m=0
d=[0]*n
t=set()
for i in range(n):
    if p[i]==i+1:
        d[i]=i+1
        m+=1
    if i!=0 and d[i]==1+d[i-1] and i-1 not in t:
        t.add(i)
print(m-len(t))

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		long n = sc.nextLong();

		if(n == 1){
			System.out.println(0);
			return;
		}

		//nが素数かどうか判定
		boolean isPrime = true;
		for(int i = 2; i <= Math.sqrt(n); i++){
			if(n % i == 0){
				isPrime = false;
				break;
			}
		}

		if(isPrime){
			System.out.println(1);
			return;
		}

		PrimeNumberGenerator pg = new PrimeNumberGenerator();

		long result = 0;
		long limit = (long)Math.sqrt(n);
		for(int i = 2; i <= limit ; i++){
//			System.out.println("i = "+i+" n = "+n);
			if(!pg.isPrime(i)){
				continue;
			}

			long j = 1;
			while(n % (long)Math.pow(i, j) == 0){
				n /= (long)Math.pow(i, j);
				j++;
				result++;
			}

			while(n % i == 0){
				n /= i;
			}
//			long count = 0;
//			while(n % i == 0){
//				n /= i;
//				count++;;
//			}
//
//			result += (long)((-1 + Math.sqrt(1 + count*8))/2.0);
		}

		if(n > 1){
			result++;
		}
		System.out.println(result);
	}
}


class PrimeNumberGenerator {
    private boolean[] isPrime= new boolean[1000001];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;

        int limit = (int)Math.sqrt(isPrime.length);
        for(int i = 3; i <= limit; i+=2){
            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= isPrime.length - 1; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
        if(index % 2 == 0 && index != 2){
            return false;
        }
        return isPrime[index];
    }
}

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


void solve(long long N){
    cout << N*N*N << endl;
}

// Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    solve(N);
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <array>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <bitset>
#include <random>
#include <functional>
#include <sstream>
#include <iomanip>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back

typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef long long LL;

int main() {
	while (true) {
		int n; cin >> n;
		if (n == 0)break;

		VI a;
		rep(i, n) {
			int x; cin >> x;
			a.pb(x);
		}
		int min = *min_element(all(a));
		int max = *max_element(all(a));
		int ans = (accumulate(all(a), 0) - min - max) / (n - 2);
		cout << ans << endl;
	}
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
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; }

const int NIL = -1;
const int INF = (1<<21);
const long long MOD = 1e9+7;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};

int main() {
  int N, M; cin >> N >> M;
  vector<pair<int,int>> v;
  for (int i = 0; i < N; ++i) {
    int a; cin >> a;
    v.push_back(make_pair(a, 1));
  }
  for (int i = 0; i < M; ++i) {
    int b, c; cin >> b >> c;
    v.push_back(make_pair(c, b));
  }
  sort(v.begin(), v.end(), greater<pair<int,int>>());
  long long ans = 0;
  int idx = 0;
  for (int i = 0; i < N; ++i) {
    ans += v[idx].first;
    v[idx].second--;
    if (v[idx].second == 0) idx++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 5340
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
#define LL long long

int main() {
    int n, cnt = 0, ans = 0, last = -1;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > last) {
            ans = max(cnt, ans);
            cnt = 0;
        } else {
            cnt++;
        }
        last = x;
    }
    cout << max(cnt, ans) << '\n';
    return 0;
}

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

int main(){
  int a, b;
  cin >> a >> b;
  
  if((a + b) % 2 == 0) cout << (a + b) / 2 << endl;
  else cout << (a + b) / 2 + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <utility>
#include <cctype>

using namespace std;

using ll = long long;
using P = pair<int, int>;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mkp(a, b) make_pair(a, b)
const int inf = 1e+9;

ll countAns(int c) {
	ll cur = 0;

	while(true) {
		if (c >= cur) {
			c -= cur;
			if (c < cur + 1) {
				return cur;
			}
			cur++;
		}
	}
	return 0;
}


int main() {
 	ll n;
 	cin >> n;
 	ll cur = n;


 	ll ans = 0;
 	for(ll p = 2; p * p <= n; p++)  {
 		ll count = 0;
 		while (cur % p == 0) {
 			cur /= p;
 			count ++;
 		}
 		ans+= countAns(count);
 	}
 	if (cur > 1) {
 		ans++;
 	}
 	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 3192
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;


int main() {
	string st;cin>>st;
	map<char,int>mp;
	for (auto c : st) {
		mp[c]++;
	}
	string s("KUPC");
	int ans=1e8;
	for (auto a:s) {
		ans=min(ans,mp[a]);
	}
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 3220
#include <iostream>
#include <cstdio>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <deque>
long long MIN(long long x, long long y) { return x < y ? x : y; }
long long MAX(long long x, long long y) { return x > y ? x : y; }
#define lowbit(x) ((x) & (-(x)))
typedef long long ll;
const int MAXN = 1e3 + 123;
using namespace std;

int H , W;
struct Node{
    int x , y;
}C , D;
char s[MAXN];
bool mp[MAXN][MAXN];
int vis[MAXN][MAXN];
int dirx[4] = {1 , -1 , 0 , 0};
int diry[4] = {0 , 0 , 1 , -1};
deque<Node> q;
void bfs() {
    q.push_back(C);
    vis[C.x][C.y] = 1;
    Node g;
    while (!q.empty()) {
        Node d = q.front();
        q.pop_front();
        //printf ("%d %d %d\n" , d.x , d.y , vis[d.x][d.y]);
        if (d.x == D.x && d.y == D.y) {
            printf ("%d\n" , vis[d.x][d.y] - 1);
            return;
        }
        for (int i = 0 ; i < 4 ; i ++) {
            g.x = d.x + dirx[i];
            g.y = d.y + diry[i];
            if (1 <= g.x && g.x <= H && 1 <= g.y && g.y <= W && vis[g.x][g.y] > vis[d.x][d.y] && !mp[g.x][g.y]) {
                vis[g.x][g.y] = vis[d.x][d.y];
                q.push_front(g);
            }
        }
        for (int i = -2 ; i <= 2 ; i ++)
            for (int j = -2 ; j <= 2 ; j ++) {
                g.x = d.x + i;
                g.y = d.y + j;
                if (1 <= g.x && g.x <= H && 1 <= g.y && g.y <= W && vis[g.x][g.y] > vis[d.x][d.y] + 1 && !mp[g.x][g.y]) {
                    vis[g.x][g.y] = vis[d.x][d.y] + 1;
                    q.push_back(g);
                }
            }
    }
    printf ("-1\n");
}

int main() {
    memset(vis , 0x7f , sizeof(vis));
    scanf ("%d %d" , &H , &W);
    scanf ("%d %d %d %d" , &C.x , &C.y , &D.x , &D.y);
    for (int i = 1 ; i <= H ; i ++) {
        scanf ("%s" , s + 1);
        for (int j = 1 ; j <= W ; j ++) {
            if (s[j] == '#')
                mp[i][j] = true;
        }
    }
    bfs();
    return 0;
}


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



int main(){
   const int N=10000;
   
    int a,b,k,j=0;
    cin>>a>>b>>k;
    
    vector<int> A(N);
    for(int i=1;i<=min(a,b);i++){
        if(a%i==0 && b%i==0){
            A.at(j)=i;
            j++;
        }
    }
    cout<<A.at(j-k)<<endl;
  return  0;
}


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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>a;
      if(a<1200)Cout("ABC");
      else if(a<2800)Cout("ARC");
      else Cout("AGC");
     

       
return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<utility>
#include<cmath>
using namespace std;
#define EPS 1e-5

//vには係数も与えられた点も入る
//cは間違っている点(仮定)
//lagrangeを満たすかどうか
bool lagrange(vector<double>& v,int n,int c){
  //一点ずつチェック
  for(int k=0;k<n;k++){
    double x=0;
    if(k==c){continue;}
    for(int i=0;i<n;i++){
      if(i==c or i==k){continue;}
      double y=1;
      for(int j=0;j<n;j++){
        if(j==c or j==k or j==i){continue;}
        y=y*(k-j)/(i-j);//情報落ち
      }
      y*=v[i];
      x+=y;
    }
    //cout <<  x << " " << v[k] << endl;
    //なぜここ0.1？
    if(abs(x-v[k])>0.9)return false;
  }
  return true;
}

int main(){
  int d;
  while(cin >> d and d!=0){
    vector<double> v(d+3);for(int i=0;i<d+3;i++)cin >>v[i];
    for(int i=0;i<d+3;i++){
      //cout << lagrange(v,d+3,i) << endl;
      if(lagrange(v,d+3,i)){cout << i << endl;break;}
    }
  }

}



Measured memory_bytes: 3140