akhauriyash/Code-Regression huggingface dataset:
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input! {
        n: usize,
        a: [usize1; n],
        b: [usize; n],
        c: [usize; n-1],
    }
    let mut ans = 0;
    let mut prev = 10000;
    for i in 0..n {
        ans += b[a[i]];

        if prev + 1 == a[i] {
            ans += c[prev];
        }
        prev = a[i];
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break

    for h in range(H):
        for w in range(W):
            if h == 0 or h == H -1 or w == 0 or w == W - 1:
                print('#', end='')
            else:
                print('.', end='')

        print()

    print()

Measured memory_bytes: 9024
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pii>
#define read(FILE)  freopen(FILE, "r", stdin);
#define out(FILE) freopen(FILE, "w", stdout);
#define clr(x, y) memset(x,y,sizeof(x));
#define IO ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(),x.end()
#define rep(i, m, n) for(ll i=m ; i<n ; i++)
#define forr(i, m, n) for(int i=m ; i<=n ; i++)
#define endl '\n'
#define pb push_back
#define re return
const int N = 1e5 + 5;
const ll OO = 1e16+7;
using namespace std;
struct point {
    ll w, price;
} arr[105];
ll n, w, dp[105][N];

ll solve(ll i, ll have) {
    if(have<0) re OO;
    if (i == n) {
        if(have==0) re 0;
        re OO;
    }
    ll &ret = dp[i][have];
    if (~ret) re ret;
    ret = min(arr[i].w + solve(i + 1, have - arr[i].price), solve(i + 1, have));
    re ret;
}

int main() {
    IO;
    cin >> n >> w;
    rep(i, 0, n) {
        cin >> arr[i].w >> arr[i].price;
    }
    memset(dp, -1, sizeof(dp));
    ll ans=0;
    rep(i,0,int(1e5+1)){
     if(solve(0,i)<=w)
         ans=i;
    }
    cout<<ans;

}

Measured memory_bytes: 82304
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
 
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);
 
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;
 
constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433;
 
template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
	ll H,N; cin >> H >> N;
	vector<ll> A(N),B(N);
	for(int i = 0; i < N; ++i) cin >> A[i] >> B[i];
	vector<ll> dp(H+1,LOWINF);
	dp[0] = 0;
	for(int i = 0; i < H; ++i) {
		if(dp[i]==LOWINF) continue;
		for(int j = 0; j < N; ++j){
			chmin(dp[min(H,i+A[j])],dp[i]+B[j]);			
		}
	}
	cout << dp[H] << endl;


    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> using vt = vector<T>;
template<class T> using vvt = vector<vt<T>>;
template<class T> using ttt = tuple<T,T>;
using tii = tuple<int,int>;
using vi = vector<int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back
#define mt make_tuple
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define DIV int(1e9+7)
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-8;
//const double PI = M_PI;
inline ll pow(ll x,ll n,ll m){ll r=1;while(n>0){if((n&1)==1)r=r*x%m;x=x*x%m;n>>=1;}return r%m;}
inline ll lcm(ll d1, ll d2){return d1 / __gcd(d1, d2) * d2;}
#define chmax(a,b) a=max(a,b)

/*Coding Space*/
int main(){
  int n,k; cin >> n >> k;
  int top = 0;
  rep(i,n-1)  top += n-2-i;
  cerr << top << endl;
  if(k > top) {
    cout << -1 << endl;
    return 0;
  }
  int cnt[n] = {}; // nodes k has cnt[k] edges;
  cnt[0] = n-1;
  cout << n-1+(top-k) << endl;
  rep(i,n){
    if(i == 0) continue;
    cout << 0+1 << ' ' << i+1 << endl;
    cnt[i]++;
  }
  int now = top;
  int now_index = 0;
  while(k - now != 0){
    if(cnt[now_index] == n-1){
      now_index++;
      continue;
    }else{
      cout << now_index+1 << ' ' << cnt[now_index]+2 << endl;
      cnt[cnt[now_index]+1]++;
      cnt[now_index]++;
      now--;
    }
  }
}


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

int main() {
    int N;
    cin >>N;
    int sum =0;
    vector<int>data(N-1);
    for(int i=0;i<N-1;i++){
        cin >>data[i];
        sum += data[i]*2;
    }
    for(int i=0;i<N-2;i++){
        int mx =0;
        mx =max(data[i],data[i+1]);
        sum -= mx;
    }
    cout << sum <<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <vector>

using cost_type = int;

cost_type sub(std::vector<cost_type> h, std::size_t k)
{
	std::vector<cost_type> dp(h.size());

	dp[0] = 0;

	std::vector<cost_type> tmp;
	tmp.reserve(k);
	for (std::size_t i = 1; i < dp.size(); ++i) {
		for (std::size_t j = i > k ? i - k : 0; j < i; ++j) {
			tmp.push_back(dp[j] + std::abs(h[j] - h[i]));
		}
		dp[i] = *std::min_element(tmp.begin(), tmp.end());
		tmp.clear();
	}

	return dp.back();
}

int main(void)
{
	std::size_t N, K;
	std::cin >> N >> K;

	std::vector<cost_type> h(N);

	for (auto& x : h) {
		std::cin >> x;
	}

	std::cout << sub(h, K) << std::endl;

	return 0;
}


Measured memory_bytes: 1408
import java.util.Scanner;
class Main{
  
  static void check_include_7(int number){
    if(number/100 == 7 || number % 10 == 7 || ((number % 100<=79)&&( number % 100 >= 70))){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
  public static void main(String args[]){
    Scanner scanner = new Scanner(System.in);
    int number = scanner.nextInt();
    check_include_7(number);
    scanner.close();
  }

}


Measured memory_bytes: 35708
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define FORR(i,a,b) for (int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))

typedef long long ll;
typedef __int128_t lll;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
void dout(double d){printf("%.12f\n",d);}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5+1;
int n, w;
ll DP[N];
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  Fill(DP, LINF);
  DP[0] = 0;
  cin >> n >> w;
  FOR(i, 0, n){
    ll a, b;
    cin >> a >> b;
    FORR(j, N, b) mins(DP[j], DP[j-b] + a);
  }
  FORR(i, N, 0) if(DP[i] <= w){
    cout << i << endl;
    break;
  }
}

Measured memory_bytes: 1152
// Online C++ compiler to run C++ online.
// Write C++ code in this online editor and run it.

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

int main() {
    string s;
    cin >> s;
    for(auto &c:s){
        if(c == '1'){
            c = '9';
        } else if (c == '9'){
            c = '1';
        }
    }
    cout << s << endl;
    //std::cout << "Hello World!";
    return 0;
}

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

typedef long long int ll;
ll n, m;
priority_queue<ll, vector<ll>, greater<ll>> mn;
priority_queue<ll> mx;
ll sl, sr, mid;
ll q;
ll b;
int main()
{
    cin >> q;
    rep(i, q)
    {
        ll x;
        cin >> x;
        if (x == 1)
        {
            ll y, z;
            cin >> y >> z;
            b += z;
            if (mx.empty() || mx.top() <= y)
            {
                mn.push(y);
                sr += y;
            }
            else
            {
                mx.push(y);
                sl += y;
                ll t = mx.top();
                sl -= t;
                sr += t;
                mn.push(t);
                mx.pop();
            }
            while (mn.size() > mx.size())
            {
                ll t = mn.top();
                mn.pop();
                sr -= t;
                mx.push(t);
                sl += t;
            }
        }
        else
        {
            ll t = mx.top();
            cout << t << " " << sr - sl + (ll)(mx.size() - mn.size()) * t + b << endl;
        }
    }
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; }
template<typename T> ostream &operator<<(ostream &os, const set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; }
template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
template<typename T> void Max(T &m, const T q) { if (m < q) m = q; }
template<typename T> void Min(T &m, const T q) { if (m > q) m = q; }
template<typename T1, typename T2> pair<T1, T2> operator+(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(pair<T1, T2> &l, pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

int H, W, N;

int main()
{
    cin >> N >> H >> W;
    cout << (N - H + 1) * (N - W + 1) << endl;
}


Measured memory_bytes: 896
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		Scanner in = new java.util.Scanner(System.in);
		int N = in.nextInt();
		int M = in.nextInt();
		int X = in.nextInt();
		int Y = in.nextInt();
		int maxX = -100;
		int x;
		for(int i=0; i<N; i++) {
			x = in.nextInt();
			if(maxX <= x) {
				maxX = x;
			}
			if(x >= Y) {
				System.out.println("War");
				System.exit(0);
			}
		}
		
		int minY = 100;
		int y;
		for(int i=0; i<M; i++) {
			y = in.nextInt();
			if(minY >= y) {
				minY = y;
			}
			if(y <= X) {
				System.out.println("War");
				System.exit(0);
			}
		}
		if(maxX >= minY) {
			System.out.println("War");
		}else {
			System.out.println("No War");
		}
		
		in.close();
	}
}


Measured memory_bytes: 23892
#include <iostream>
#include <cmath>
using namespace std;
int main(void)
{
    int n;
    cin >> n;
    int count = 0, i, j;
    for (i = 1; i < n; i++)
    {
        int tmp = n - i;
        double sq = sqrt(tmp);
        for (j = 1; j <= sq; j++)
        {
            if (tmp % j == 0)
            {
                if (sq == (double)j)
                {
                    count++;
                }
                else
                {
                    count += 2;
                }
            }
        }
    }
    cout << count << endl;
    return 0;
}

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

int main(){
  int N,D;
  cin>>N>>D;
  if(N%(2*D+1)==0){
    cout<<N/(2*D+1)<<endl;
  }
  else{
    cout<<N/(2*D+1)+1<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n = 200005;
int n, a[max_n];
ll dp[max_n];
ll sum[max_n];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a+i);
    sum[1] = a[1];
    for(int i = 2; i <= n; i++) {
        sum[i] = sum[i-2] + a[i]; 
    }
    for(int i = 2; i <= n; i++) {
        if(i&1) {
            dp[i] = max(dp[i-1], dp[i-2] + a[i]);
        }
        else {
            dp[i] = max(sum[i-1], a[i] + dp[i-2]);
        }
    }
    printf("%lld\n", dp[n]);
    return 0;
}

Measured memory_bytes: 7624
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
s=sum(A)
import collections
a= collections.Counter(A)
for i in range(Q):
    B,C=map(int,input().split())
    n=a[B]
    s+=(C-B)*n
    print(s)
    a[B]=0
    a[C]=a[C]+n

Measured memory_bytes: 23836
Fixnum.class_eval {
  def is_prime?
    return true if self == 2
    return false if self < 2 or self % 2 == 0

    3.step(Math.sqrt(self).ceil, 2) { |i|
      return false if self % i == 0
    }
    true
  end
}

puts STDIN.read.split("\s")[1..-1].map(&:to_i).map(&:is_prime?).select { |x| x }.size

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
 
#define hell 1000000007
#define PI acos(-1.0)
#define S second
#define F first
#define lli long long int
#define li long int
#define ld long double
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
 
#define run(j, n) for(auto ii=j;ii!=n;ii++)
#define out(j, n) for(auto ii=j;ii!=n;ii++) cout<<(*ii)<<" ";


int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed << showpoint;
cout << setprecision(11);

int a;cin>>a;
cout<<(a+a*a+a*a*a);

return 0;
}

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

vector<ll> par(100000); //親

void init(int n){
    for(int i=0;i<n;i++) par[i]=-1;
}

//親を求める
int root(int x){
    if(par[x]<0) return x;
    return par[x]=root(par[x]); //検索毎に根を親に組み替える
}

//集合のサイズを求める
int size(int x){
    return -par[root(x)];
}

//X集合とY集合を統合
bool unite(int x,int y){
    //Xの根とYの根を接続
    x=root(x);
    y=root(y);
    if(x==y) return false;  //すでに統合済み

    if(size(x)<size(y)) swap(x,y); //大きい集合(X)に小さい集合(Y)を接続
    par[x]+=par[y]; //サイズ増加
    par[y]=x; //根の組み替え
    return true;
}

ll combination(ll n,ll m){
	ll nume=1; //分子
	for(int i=0;i<m;i++) nume*=(n-i);
	ll deno=1; //分母
	for(int i=1;i<=m;i++) deno*=i;
	ll res=nume/deno;
	return res;
}

int main(){
    ios::sync_with_stdio(false);
	ll n,m;
	cin>>n>>m;
	ll ans=combination(n,2);
	stack<ll> sta;
	init(n);
	vector<int> A(m),B(m);
	for(int i=0;i<m;i++){
		cin>>A[i]>>B[i];
		A[i]--; B[i]--;
	}
	for(int i=m-1;i>=0;i--){
		sta.push(ans);
		ll x=size(A[i]),y=size(B[i]);
		if(unite(A[i],B[i])){
			if(max(size(A[i]),size(B[i]))==2) ans--;
			else ans-=x*y;
		}
	}
	while(!sta.empty()){
		ll tmp=sta.top();
		cout<<tmp<<endl;
		sta.pop();
	}
	return 0;
}

Measured memory_bytes: 3484
#include <iostream>
#include <vector>
#include <climits>

std::vector<std::vector<int>> data;
int X;

int dfs(int deep,std::vector<int> us,int mon){
 if(deep==-1){
  for(int i=0;i<us.size();i++){
   if(us[i]<X){
    return INT_MAX;
   }
  }
  return mon;
 }else{
  int v1=dfs(deep-1,us,mon);
  for(int i=0;i<us.size();i++){
   us[i]+=data[deep][i+1];
  }
  int v2=dfs(deep-1,us,mon+data[deep][0]);

  if(v1<v2){
   return v1;
  }else{
   return v2;
  }
 }
}


int main(){
 int N,M;
 std::cin>>N>>M>>X;
 
 std::vector<int> us(M,0);
 data.resize(N);

 int tmp;
 for(int i=0;i<N;i++){
  for(int j=0;j<M+1;j++){
   std::cin>>tmp;
   data[i].emplace_back(tmp);
  }
 }
/*
 for(int i=0;i<N;i++){
  for(int j=0;j<M+1;j++){
   std::cout<<data[i][j]<<" ";
  }
  std::cout<<std::endl;
 }
*/

 int ans=dfs(N-1,us,0);
 if(ans==INT_MAX){
  ans=-1;
 }
 std::cout<<ans<<std::endl;
}

Measured memory_bytes: 3632
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.Map;
import java.util.PriorityQueue;
import java.math.BigInteger;
    
public class Main{

static final InputStream in=System.in;
static final PrintWriter out=new PrintWriter(System.out);
static final int INF=Integer.MAX_VALUE/2;

public static void main(String[] args) throws IOException{
InputReader ir=new InputReader(in);
while(true){
int n=ir.nextInt();
if(n==0) break;
HashMap<String,String> map=new HashMap<String,String>();
StringBuilder sb=new StringBuilder();
while(n-->0) map.put(ir.next(),ir.next());
int m=ir.nextInt();
while(m-->0){
String str=ir.next();
sb.append((map.containsKey(str))?map.get(str):str);
}
out.println(sb.toString());
}
out.flush();
}

static class InputReader {
private InputStream in;
private byte[] buffer=new byte[1024];
private int curbuf;
private int lenbuf;

public InputReader(InputStream in) {this.in=in;}
  
public int readByte() {
if(lenbuf==-1) throw new InputMismatchException();
if(curbuf>=lenbuf){
curbuf= 0;
try{
lenbuf=in.read(buffer);
}
catch (IOException e) {
throw new InputMismatchException();
}
if(lenbuf<=0)
return -1;
}
return buffer[curbuf++];
}

public boolean isSpaceChar(int c){return !(c>=33&&c<=126);}

private int skip() {int b; while((b = readByte())!=-1&&isSpaceChar(b)); return b;}

public String next() {
int b=skip();
StringBuilder sb=new StringBuilder();
while(!isSpaceChar(b)){
sb.appendCodePoint(b);
b=readByte();
}
return sb.toString();
}
 
public int nextInt() {
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
int res=0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}

public long nextLong() {
int c=readByte();
while (isSpaceChar(c)) c=readByte();
boolean minus=false;
if (c=='-') {
minus=true;
c=readByte();
}
long res = 0;
do{
if(c<'0'||c>'9') throw new InputMismatchException();
res=res*10+c-'0';
c=readByte();
}while(!isSpaceChar(c));
return (minus)?-res:res;
}

public int[] toIntArray(int n){
int[] a=new int[n];
for(int i=0;i<n;i++) a[i]=nextInt();
return a;
}
}
}

Measured memory_bytes: 37364
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int l=s.length();
	int ans=0;
	for(int i=0;i<l;i++)
		if(s[i]=='A')
			if(s[i+1]=='B')
				if(s[i+2]=='C')
					ans++;
	cout<<ans<<endl;
	return 0;
}

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

using namespace std;


int main() {
    int N,K,t=0;
    cin >> N >> K;
    vector<int> ex(20);
    double ans=0;

    while(N*pow(2,t)<K){
        t++;
    }

    for(int i = N;i >= 1;i--){
        if(i*pow(2,t) >=K){
            ex[t]++;
        }else{
            t++;
            ex[t]++;
        }
    }

    for(int i = 0; i <19;i++){
        ans+= (ex[i]*pow(0.5,i))/N;
    }


    cout << fixed << setprecision(12) << ans << endl;

}


Measured memory_bytes: 256
#pragma region template
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9 + 7, MAX = 1e18, larg = 1e5, INF = -1e9;
long long A, B, C, D, E, F, G, H, I, J, K, L, N, M, O, P, Q, R, S, T, U, V, W;
typedef long long ll;
typedef pair<ll, ll> Pa;

vector<ll> prime_factor(ll num){
    vector<ll> vec;
    ll a = 2;
    while(num >= a*a){
        if(num%a==0){
            vec.push_back(a);
            num /= a;
        }else{
            a++;
        }
    }
    vec.push_back(num);
    return vec;
}

map<int, int> mp;
int main() {
    cin >> N;
    for(int i=2;i<=N;i++){
        vector<ll> vec = prime_factor(i);
        rep(i, vec.size()){
            if(mp.find(vec[i]) == mp.end()) mp[vec[i]] = 1;
            else mp[vec[i]]++;
        }
    }
    ll sum = 1;
    for(auto itr = mp.begin(); itr != mp.end(); itr++){
        sum = (sum * (itr->second+1))%MOD;
    }
    cout << sum;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define max3(a,b,c) ((a>b)?(a>c)?a:c:(b>c)?b:c)
#define min3(a,b,c) ((a<b)?(a<c)?a:c:(b<c)?b:c)
#define REP(i,a,n) for(ll i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define MAX 1000000001

int prime[1000001];
void SieveOfEratosthenes(){ 
    memset(prime, -1, sizeof(prime)); 
    prime[1]=1;
    for(ll p=2; p<=1000000 ; p++){
        if(prime[p] == -1){
            prime[p]=p;
            for(ll i=p*p; i<=1000000 ; i += p){
                if(prime[i]==-1){
                    prime[i]=p;
                }
            }
        }
    }
    return;
}

int main(){
	fast;
	int test=1;
	SieveOfEratosthenes();
	//cin >> test;
	while(test--){
	    int n;
	    cin >> n;
	    map<int,int>m;
	    bool ok=1;
	    for(int i=0 ; i<n ; i++){
	        int x;
	        cin >> x;
	        set<int>s;
	        while(x>1){
	            s.insert(prime[x]);
	            x/=prime[x];
	        }
	        for(auto &j:s){
	            m[j]++;
	            if(m[j]>1){
	                ok=0;
	            }
	        }
	    }
	    if(ok){
	        cout << "pairwise coprime" << endl;
	    }else{
	        ok=1;
	        for(auto &i:m){
	            if(i.second==n){
	                ok=0;
	            }
	        }
	        if(ok){
	            cout << "setwise coprime" << endl;
	        }else{
	            cout << "not coprime" << endl;
	        }
	    }
	}
	return 0;
}

Measured memory_bytes: 11168
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
const int mod=1e9,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N=100001;

int main(){
  int N;
  int a[MAX_N];
  bool passed[MAX_N];
  cin >> N ;
  rep(i,N){
    cin >> a[i] ;
    a[i]--;
  }
  fill(passed,passed+N,false);
  int now=0;
  int cnt=0;
  while(now!=1){
    if(passed[now]){
      cnt=-1; break;
    }
    passed[now]=true;
    now=a[now];
    cnt++;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<functional>
#include<string>
#include<iomanip>
#include<map>
#include<utility>
#include<string>
#include<unordered_map>
#include <queue>

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

using namespace std;

#define min_3(a, b, c) min(a, min(b, c))
#define max_3(a, b, c) max(a, max(b, c))
typedef long long ll;

int main()
{
    int n, m;
    cin >> n >> m;
    priority_queue<int> q; //要素を順に並べてくれるキュー
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        q.push(a);
    }
    for(int i = 0; i < m; i++){
        int a = q.top();
        q.pop();
        q.push(a/2);
    }
    ll sum = 0;
    for(int i = 0; i < n; i++){
        sum += q.top();
        q.pop();
    }

    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

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

    ll X, Y;
    cin >> X >> Y;

    string ans = "No\n";
    Rep (i, 100) {
        Rep (j, 100) {
            if (i*2 + j*4 == Y and i+j == X) {
                ans = "Yes\n";
            }
        }
    }

    cout << ans;
}

Measured memory_bytes: 3624
const int isDebugMode = 1;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
const long long dy[] = {-1, 0, 0, 1};
const long long dx[] = {0, -1, 1, 0};
string abc = "abcdefghijklmnopqrstuvwxyz";
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for (const auto &e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void pt(){cout << endl; return;}
template<class Head> void pt(Head&& head){cout << head; pt(); return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
void dpt(){if(!isDebugMode) return; cout << endl; return;}
template<class Head> void dpt(Head&& head){if(!isDebugMode) return; cout << head; pt(); return;}
template<class Head, class... Tail> void dpt(Head&& head, Tail&&... tail){if(!isDebugMode) return; cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){if(!isDebugMode) return; rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){if(!isDebugMode) return; rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}
template<class T1, class T2> long long recgcd(T1 a, T2 b){return a % b ? recgcd(b , a % b) : b;}
bool valid(long long H, long long W, long long h, long long w) { return 0 <= h && h < H && 0 <= w && w < W; }

int main(){
    ll N; cin >> N;
    ll ac = 0;
    ll wa = 0;
    ll tle = 0;
    ll re = 0;
    rep(i, N){
        string s; cin >> s;
        if(s == "AC") ac++;
        if(s == "WA") wa++;
        if(s == "TLE") tle++;
        if(s == "RE") re++;
    }
    pt("AC x", ac);
    pt("WA x", wa);
    pt("TLE x", tle);
    pt("RE x", re);
}

Measured memory_bytes: 3596
import sys
sys.setrecursionlimit(10**6)
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

n,d=MI()
l=2*d+1
ans=(n+l-1)//l
#for i in range(n):
print(ans)





Measured memory_bytes: 38256
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
using namespace std;
#define Ma_PI 3.141592653589793
#define eps 0.00000000000000000000000001
#define LONG_INF 3000000000000000000
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007
#define REP(i,n) for(long long i = 0;i < n;++i)                                                                             
#define seg_size 524288
double dp[60000][300] = {};
int main() {
	int n;
	cin >> n;
	vector<pair<double, double>> wow;
	int total_time = 0;
	REP(i, n) {
		double a, b;
		cin >> a;
		total_time += 2 * a;
		wow.push_back(make_pair(a * 2,0));
	}
	REP(i, n) {
		cin >> wow[i].second;
		wow[i].second *= 2.0;
	}
	wow.push_back(make_pair(1, 0));
	for (int i = 0;i < 60000;++i) {
		for (int q = 0;q < 300;++q) {
			dp[i][q] = -1;
		}
	}
	//time / speed
	dp[0][0] = 0;
	int now_itr = 0;
	int now_time = 0;
	for (int sec = 0;sec < total_time;++sec) {
		for (int q = 0;q <= 250;++q) {
			if (dp[sec][q] != -1) {
				if (q != 0) {
					//loss speed
					dp[sec+1][q - 1] = max(dp[sec+1][q - 1], dp[sec][q] + (double)((double)q / (double)4) - 0.125);
				}
				dp[sec + 1][q] = max(dp[sec + 1][q], dp[sec][q] + (double)((double)q / (double)4));
				if (q < wow[now_itr].second) {
					dp[sec+1][q+1] = max(dp[sec + 1][q+1], dp[sec][q] + (double)((double)q / (double)4)+0.125);
				}
			}
		}
		now_time++;
		if (now_time == wow[now_itr].first) {
			now_time = 0;
			now_itr++;
			for (int q = wow[now_itr].second + 1;q < 300;++q) {
				dp[sec + 1][q] = -1;
			}
		}
	}
	cout <<fixed << setprecision(20) << dp[total_time][0] << endl;
	return 0;
}

Measured memory_bytes: 140928
#include <stdio.h>
#include <limits.h>

char S[114514];

int main(void) {
	int i;
	char asumikana[(int)UCHAR_MAX + 1] = {0};
	if (scanf("%114513s", S) != 1) return 1;
	for (i = 0; S[i] != '\0'; i++) {
		asumikana[(unsigned char)S[i]] = 1;
	}
	for (i = 'a'; i <= 'z'; i++) {
		if (!asumikana[i]) {
			printf("%c\n", i);
			return 0;
		}
	}
	puts("None");
	return 0;
}


Measured memory_bytes: 256
n, m, l = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(n)]
B = [[int(b) for b in input().split()] for _ in range(m)]
C = [[0] * l for _ in range(n)]

for i in range(n):
    for j in range(l):
        for k in range(m):
            C[i][j] += A[i][k] * B[k][j]

for c in C:
    print(*c)


Measured memory_bytes: 7040
#[allow(unused_imports)]
use std::cmp::{max, min, Ordering};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::iter::FromIterator;
#[allow(unused_imports)]
use std::io::stdin;

mod util {
    use std::io::stdin;
    use std::str::FromStr;
    use std::fmt::Debug;

    #[allow(dead_code)]
    pub fn line() -> String {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.trim().to_string()
    }

    #[allow(dead_code)]
    pub fn gets<T: FromStr>() -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        let mut line: String = String::new();
        stdin().read_line(&mut line).unwrap();
        line.split_whitespace()
            .map(|t| t.parse().unwrap())
            .collect()
    }
}

#[allow(unused_macros)]
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
                    get!($t)
                   ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
                    get!($($t),*)
                   ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

const M: u64 = 1000000007;

fn main() {
    let n = get!(usize);
    let s = util::line().chars().count();

    let mut dp = vec![vec![0; n + 1]; n + 1];
    dp[0][0] = 1;

    for i in 1..n + 1 {
        dp[i][0] = dp[i - 1][0];
        for j in 0..n + 1 {
            if j + 1 < n + 1 {
                dp[i][j + 1] += dp[i - 1][j];
                dp[i][j + 1] %= M;
            }
            if j > 0 {
                dp[i][j - 1] += dp[i - 1][j] * 2 % M;
                dp[i][j - 1] %= M;
            }
        }
    }

    println!("{}", dp[n][s]);
}


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

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

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

#define MAXKN 100001

bool is_prime[MAXKN];

// x^n in mod
ll modpow(ll x, ll n, ll mod){
  if(n==0) return 1;

  if(n%2==0){
    return modpow(x*x%mod, n/2, mod) % mod;
  }else{
    return x * modpow(x, (n-1), mod) % mod;
  }
}

int main(){
  ll n, k;cin>>n>>k;
  rep(i, MAXKN)is_prime[i]=true;
  is_prime[0]=is_prime[1]=false;
  for(int i=2; i<MAXKN; i++){
    for(int j=i*2; j<MAXKN; j+=i)is_prime[j]=false;
  }

  ll no1_count = 0;
  ll result = 0;

  ll one_count = modpow(k, n, MOD);
  vector<ll> counts;
  counts.push_back(0);
  rep1(a, k) counts.push_back( modpow(k/a, n, MOD) );

  rrep1(a, k){
    for(int i=a*2; i<=k; i+=a) counts[a]=(counts[a]-counts[i]+MOD)%MOD;
    result += a*counts[a];
    result %= MOD;
  }

  cout<<result<<endl;

  return 0;
}



Measured memory_bytes: 4356
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
int mod = 1000000007;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
ll modpow(ll a, ll b, ll _mod) { return b ? modpow(a * a % _mod, b / 2, _mod) * (b % 2 ? a : 1) % _mod : 1; }
template<class T> ostream& operator << (ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator << (ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<typename T >inline istream& operator >> (istream& is, vector<T>& v) { rep(j, sz(v)) is >> v[j]; return is; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }


void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(10);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n);
  cin >> a;
  vector<pii> v(m);
  rep(i, m) cin >> v[i].S >> v[i].F;
  sort(all(v), greater<pii>()); // debuged, greater
  priority_queue<int> q;
  [&]() {
    rep(i, m) {
      rep(j, v[i].S) {
        q.push(v[i].F);
        if (sz(q) == n) return;
      }
    }
  }();
  rep(i, n) q.push(a[i]);
  ll ans = 0;
  rep(i, n) {
    ans += q.top();
    q.pop();
  }
  cout << ans << endl;
}


Measured memory_bytes: 2552
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, x, d = 100000000, sum = 0;
  cin >> N;
  x = N;
  
  for (int i = 0; i < 9; i++) {
  sum += x / d;
  x %= d;
  d /= 10;  
  }
  
  if (N % sum == 0) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)
    {cout<<"Hello World";}
    else if(n==2)
    {
        int a,b;
        cin>>a>>b;
        int s = a+b;
        cout<<s;
    }
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

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

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

  vector<int> A(9),B(9,0);
  rep(i,9) cin>>A[i];

  int n;
  cin>>n;
  
  int x;
  rep(i,n){
    cin>>x;
    rep(j,9){
      if(A[j]==x) B[j]=1;
    }
  }
  
  bool b=false;
  if(B[0]==1 && B[1]==1 && B[2]==1) b=true;
  if(B[3]==1 && B[4]==1 && B[5]==1) b=true;
  if(B[6]==1 && B[7]==1 && B[8]==1) b=true;
  if(B[0]==1 && B[3]==1 && B[6]==1) b=true;
  if(B[1]==1 && B[4]==1 && B[7]==1) b=true;
  if(B[2]==1 && B[5]==1 && B[8]==1) b=true;
  if(B[0]==1 && B[4]==1 && B[8]==1) b=true;
  if(B[2]==1 && B[4]==1 && B[6]==1) b=true;
  
  if(b) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}

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

#define Int long long int
#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()

int main(){
    int n;
    cin >> n;
    int a;
    cin >> a;
    if(a<n%500) NO;
    else YES;
}


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

using namespace std;

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

#define each(i,a) for (auto&& i : a)
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    each(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    rep(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector< vector<T> >& vec) {
    rep(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

bool is_connected(const ll n, const vector<P>& edges, const ll ignore_idx) {
    const ll m = edges.size();
    vector<vector<ll>> G(n);
    rep(i, m) {
        if (i == ignore_idx) continue;
        ll a, b; tie(a, b) = edges[i];
        G[a].pb(b);
        G[b].pb(a);
    }
    ll res = 0;
    stack<ll> S; S.push(0);
    vector<bool> used(n, false);
    used[0] = true;
    while ( !S.empty() ) {
        ll v = S.top(); S.pop();
        each(to, G[v]) {
            if (used[to]) continue;
            used[to] = true;
            S.push(to);
        }
    }
    rep(i, n) {
        if (!used[i]) return false;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, m; cin >> n >> m;
    vector<P> edges;
    rep(i, m) {
        ll a, b; cin >> a >> b; --a, --b;
        edges.pb({a, b});
    }
    ll ans = 0;
    rep(i, m) {
        if (!is_connected(n, edges, i)) ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

#define N 2000001

int B[N], C[N];
int n;

void countingSort(int A[], int B[], int k){
  int i, j;
  
  for(i = 0; i <= k; i++) C[i] = 0;
  
  for(j = 1; j <= n; j++) C[A[j]]++;
  
  for(i = 1; i <= k; i++) C[i] = C[i] + C[i - 1];
  
  for(j = n; j >= 1; j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  
  for(i = 1; i <= n; i++){
    printf("%d", B[i]);
    if(i != n) printf(" ");
}
  
  printf("\n");
}

int main(){
  int A[N];
  int i, k = 0;
  
  scanf("%d", &n);
  
  for(i = 1; i <= n; i++){
    scanf("%d", &A[i]);
    if(k < A[i]) k = A[i];
  }
  
  countingSort(A, B, k);
  
  return 0;
}

Measured memory_bytes: 16600