akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Specialized;
using System.Linq;
using System.Numerics;

namespace AtCoderWorkspace
{
    public class Solver
    {
        public void Solve()
        {
            var cin = new Scanner();
            var n = cin.nextInt();
            var k = cin.nextInt();
            var x = cin.ArrayInt(n);

            var ans = 0;
            for (int i = 0; i < n; i++)
            {
                ans += Math.Min(x[i] * 2, (k - x[i]) * 2);
            }

            Console.WriteLine(ans);
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public int[] DPArrayInt(int N, int ex)
        {
            int[] Array = new int[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt();
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public long[] DPArrayLong(int N, int ex)
        {
            long[] Array = new long[N + ex];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong();
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }

    class Program
    {
        static void Main(string[] s) => new Solver().Solve();
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define square(x) pow(x 2.0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
#define max_queue(x) priority_queue<x>
#define min_queue(x) priority_queue<x, vector<x>, greater<x>>
#define big_sort(v) sort(all(v), [](int a, int b) { return a > b; })//大きい順にソート
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
#define co(x) cout << x << endl;
#define cins(n,v) rep(i,n){cin >> v.at(i);}
#define couts(v) rep(i,v.size()){cout << v.at(i) << endl;}
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
/*
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
*/
int main() {
  ll n,x,count;
  cin >> n >> x;
  while(true){
    rep(i,n-2){
      REP(j,i+1,n-1){
        REP(k,j+1,n){
          if(i+j+k+3==x){count++;}
        }
      }
    }
    cout << count << endl;
    count = 0;
    cin >> n >> x;
    if(n==0||x==0){return 0;}
  }
}



Measured memory_bytes: 3088
function main(input) {
  	input = input.split(" ");

  	var BasePoint = input[0];
  	var Apoint = input[1];
  	var Bpoint = input[2];
  	//console.log(BasePoint,input[1],input[2]);
  
  	AbetweenBase = BasePoint - Apoint;
  
  	BbetweenBase = BasePoint- Bpoint;
  
  	if (Math.abs(AbetweenBase) > Math.abs(BbetweenBase)){
     	console.log("B"); 
    } else {
      	console.log("A");
    } 
  	
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){
  int H, W;
  cin >> H >> W;
  char map[H][W];
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++) cin >> map[i][j];
  }
  
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cout << map[i][j];
    }
    cout << endl;
    for(int j=0; j<W; j++){
      cout << map[i][j];
    }
    cout << endl;
  }
}

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

struct Dice {
    int s[6];
    void roll (char c) {
        int b;
        if (c == 'E') {
            b = s[0];
            s[0] = s[3];
            s[3] = s[5];
            s[5] = s[2];
            s[2] = b;
        }
        if (c == 'W') {
            b = s[0];
            s[0] = s[2];
            s[2] = s[5];
            s[5] = s[3];
            s[3] = b;
        }
        if (c == 'N') {
            b = s[0];
            s[0] = s[1];
            s[1] = s[5];
            s[5] = s[4];
            s[4] = b;
        }
        if (c == 'S') {
            b = s[0];
            s[0] = s[4];
            s[4] = s[5];
            s[5] = s[1];
            s[1] = b;
        }
        if (c == 'R') {
            b = s[1];
            s[1] = s[2];
            s[2] = s[4];
            s[4] = s[3];
            s[3] = b;
        }
    }
    int top () {
        return s[0];
    }
    int front () {
        return s[1];
    }
    int left () {
        return s[3];
    }
    int right () {
        return s[2];
    }
};

int main() {

  Dice d;

  for (int i = 0; i < 6; i++) {
      cin >> d.s[i];
  }

  int q;
  cin >> q;

  for (int i = 0; i < q; i++) {
    int ue, mae;
    cin >> ue >> mae;
    if (d.left() == ue) {
        d.roll('E');
    }
    if (d.right() == ue) {
        d.roll('W');
    }
    while (d.top() != ue) {
        d.roll('N');
    }
    while (d.front() != mae) {
        d.roll('R');
    }
    cout << d.right() << endl;
  }

  return 0;

}


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

int main() {
  int N;
  vector<int> vec(N);
  int A = 0, B = 0;
  
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    cin >> vec[i];
  }
  
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      A += vec[i];
    }
    else {
      B += vec[i];
    }
  }

  cout << A - B << endl;
}

Measured memory_bytes: 3792
N=int(input())
W=[0]*N
for i in range(N):
  W[i]=input()
for i in range(N-1):
  A=W[i]
  B=W[i+1]
  if A[-1]!=B[0]:
    print('No')
    exit()
  elif W.count(B)>=2:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3060
# coding: utf-8

class UnionFind:
    def __init__(self,N):
        self.par = [i for i in range(N)]
        self.rank = [1]*N
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)
        
class Edge:
    def __init__(self, u, v, cost):
        self.u = u
        self.v = v
        self.cost = cost

def kruskal():
    es.sort(key=lambda x: x.cost)
    uf = UnionFind(V)
    res = 0
    for i in range(E):
        if not uf.same(es[i].u, es[i].v):
            uf.unite(es[i].u, es[i].v)
            res += es[i].cost
            
    return res

V = int(input().rstrip())
E = 0
es = []
for i in range(V):
    line = list(map(int, input().rstrip().split()))
    for j in range(V):
        if line[j] != -1:
            es.append(Edge(i,j,line[j]))
            E += 1

ans = kruskal()
print(ans)


Measured memory_bytes: 7176
//
// Created by 伊東麻沙美 on 2019/10/22.
//

#include<iostream>
#include<algorithm>

using namespace std;


int main(){

    char b;
    cin>>b;

    if(b=='A'){
        cout<<'T';
    }
    if(b=='T'){
        cout<<'A';
    }
    if(b=='C'){
        cout<<'G';
    }
    if(b=='G'){
        cout<<'C';
    }
    return 0;
}

Measured memory_bytes: 256
import Control.Applicative
import Data.List

getTableLines :: String -> [[Int]]
getTableLines tb = (map (map read) . map words . lines) tb

getTableRows :: String -> [[Int]]
getTableRows tb = (transpose . getTableLines) tb

getAnswer :: String -> String
getAnswer tb = (unlines . map unwords . map (map show)) (a ++ [b])
    where
        a = addLinesSum tb
            where
                addLinesSum :: String -> [[Int]]
                addLinesSum tb = [l ++ [sum l]| l <- (getTableLines tb)]
        b = getRowsSumAndTotal tb
            where
                getRowsSumAndTotal :: String -> [Int]
                getRowsSumAndTotal tb = [sum r | r <- rs] ++ [sum $ map sum rs]
                    where
                        rs = getTableRows tb
                

main :: IO ()
main = do
    _ <- getLine
    putStr =<< getAnswer <$> getContents

Measured memory_bytes: 6560
#include<bits/stdc++.h>
#define ll long long
#define ld double
#define P pair<ll,ll>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int n,a[200005];
ll s[200005],ans=1e18;
int print(int x){
	printf("%d\n",x);
	return x;
}
P search(int L,int R){
	int mid,l=L,r=R;
	while(l<r){
		mid=l+r>>1;
		if(s[R]-s[mid]*2+s[L-1]>0)l=mid+1;
		else r=mid-1;
	}
	ll res=1e18,a,b;
	for(int i=l-1;i<=l+1;++i){
		if(i==0||i==n)continue;
		if(abs(s[R]-s[i]*2+s[L-1])<res)res=abs(s[R]-s[i]*2+s[L-1]),a=s[R]-s[i],b=s[i]-s[L-1];
	}
	return make_pair(a,b);
}
int main(){
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i];
	for(int i=2;i<n;++i){
		P l=search(1,i),r=search(i+1,n);
		ll Min=min(min(l.first,l.second),min(r.first,r.second)),
		   Max=max(max(l.first,l.second),max(r.first,r.second));
		ans=min(Max-Min,ans);
	}
	printf("%lld",ans);
}

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

long long N,M;
long long edges[100010]={0};



int main(){
    long long A[100010],B[100010],H[100010];
cin>>N>>M;
    for( long long i=0; i<N; i++) cin>>H[i];
    
    for(long long i=0; i<M; i++){
       long long x,y;
        cin>>x>>y;
        
        if(H[x-1]<=H[y-1])edges[x-1]=1;
        if(H[x-1]>=H[y-1]) edges[y-1]=1;
    }
    long long counter=0;
    for(long long i=0; i<N; i++){
        if(edges[i]==0) counter++;
    }
    cout<<counter<<endl;
}

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

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

    for(int i = 0; i <= n; i++){
        int t = i;
        int cc = 0;
        while(t > 0){
            cc += t % 6;
            t /= 6;
        }
        t = n - i;
        while(t > 0){
            cc += t % 9;
            t /= 9;
        }
        ans = min(ans, cc);
    }
    cout << ans << endl;
    return 0;
}

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

using ll = long long;
using P = pair<ll, int>;    // (重み, 縦横)

int main() {
    int W, H;
    cin >> W >> H;

    const int MAXN = 200000;
    static P elts[MAXN];

    for (int i = 0; i < W; i++) {
        cin >> elts[i].first;
        elts[i].second = 0;
    }
    for (int i = 0; i < H; i++) {
        cin >> elts[W + i].first;
        elts[W + i].second = 1;
    }

    int N = W + H;
    sort(elts, elts + N);

    ll counter[2] = {W + 1, H + 1};
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        P& p = elts[i];

        ans += p.first * counter[p.second ^ 1];
        counter[p.second]--;
    }
    cout << ans << endl;

    return 0;
}

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

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

int main(void){
	long long N,ans = 1;
	int sum = 0;
	cin >> N;
	while(N > 1){
		N /= 2;
		sum++;
	}
	REP(i,sum) ans = ans*2+1;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
N, M = map(int, input().split())
A = list(input() for _ in range(N))
B = list(input() for _ in range(M))
b = len(B[0])

ans = "No"
for i in range(N-(M-1)):
  n = -1
  c = 0
  for j in range(M):
    if B[j] in A[i+j]:
      if n < 0:
        n = A[i + j].index(B[j])
        c += 1
      else:
        if B[j] in A[i + j][n: n + b + 1]:
          c += 1
  if c == M:
    ans = "Yes"
print(ans)

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

int main(){

  int n,m,x,y;
  cin>>n>>m>>x>>y;
  
  vector<int> datax(n);
  vector<int> datay(m);
  
  for (int i=0;i<n;i++){
    cin>>datax.at(i);
  }
  
  for (int i=0;i<m;i++){
    cin>>datay.at(i);
  }
  
  datax.push_back(x);
  datay.push_back(y);
  
  sort(datax.begin(),datax.end());
  sort(datay.begin(),datay.end());
  
  if (datax.at(n)<datay.at(0)){
    cout<<"No War"<<endl;
  }
  
  else {
    cout<<"War"<<endl;
  }
  
  

}
  













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

int main() {
	int N; cin >> N;
	char c;
	for( int i = 0; i < N; i++ ){
		cin >> c;
		if(c == 'Y'){cout << "Four" << endl; return 0;}
	}
	
	
	cout << "Three" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  string s;
  cin>>s;
  int ans1=0,ans2=0;
  rep(i,s.size()){
    if(i%2==0){
      if(s[i]=='0') ans1++;
      if(s[i]=='1') ans2++;
    }
    if(i%2==1){
      if(s[i]=='1') ans1++;
      if(s[i]=='0') ans2++;
    }
  }
  cout<<min(ans1,ans2);
}

Measured memory_bytes: 512
#include <stdio.h>

#define MAX 5000

int main(void)
{
    int i, j;

    int n;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }

        int num[MAX];
        for (i = 0; i < n; i++) {
            scanf(" %d", num + i);
        }

        int max = -100000;
        for (i = 0; i < n; i++) {
            int sum_ij;
            int max_i;
            max_i = sum_ij = num[i];
            for (j = i + 1; j < n; j++) {
                sum_ij += num[j];
                if (sum_ij > max_i) {
                    max_i = sum_ij;
                }
            }
            if (max_i > max) {
                max = max_i;
            }
        }

        printf("%d\n", max);
    }

    return 0;
}

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

int main () {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  int b = 1, c = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == b) {
      b ++;
      c ++;
    }
  }
  if (c == 0) {
    cout << -1 << endl;
  }
  else {
    cout << n-c << endl;
  }
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace  std;
#define ll long long
bool check(string s,int k){
	int n=s.length();
	if((n-k) % 2==1) return 0;
	n-=k;
	for(int i=0;i<n/2;i++){
		if(s[i]!=s[n/2+i]) return 0;
	}
	return 1;
}
int main(){
	string a;
	cin>>a;
	int n=a.length();
	for(int i=1;i<n;i++){
		if(check(a,i)){
			cout<<n-i;
			break;
		}
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}




int main() {
	ll N;
	cin >> N;
	vector<ll> A(N);
	bool check = true;
	rep(i, N) {
		cin >> A[i];
		if (A[i] > N - 1)check = false;
	}
	ll an = 0;
	while (check==false) {
		check = true;
		ll S = 0;
		rep(i, N) {
			S += A[i] / N;
		}
		an += S;
		rep(i, N) {
			A[i] += (S - A[i] / N) - (A[i] / N) * N;
			if (A[i] > N - 1)check = false;
		}
	}
	cout << an << endl;
}


Measured memory_bytes: 3592
#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>;

const int INF = 1001001001;

int a[12][12];

int main() {
 int A,P;
 cin>>A>>P;
 cout<<(A*3+P)/2<<endl;
 
  return 0;
}

Measured memory_bytes: 256
<?php
  list($Q) = explode(" ", trim(fgets(STDIN)));

  $P = new PrimeNumber();
  $p = $P->createPrimeNumber(100000);

  $key = array_flip($p);

  $like2017 = 0;
  $a = array_fill(0, 1000001, 0);
  for ($i=3; $i<=1000000; $i++) {
    if(isset($key[$i])){
      if(isset($key[($i+1)/2])){
        $like2017++;
      }
    }
    $a[$i] = $like2017;
  }
  
  for ($i=0; $i<$Q; $i++) {
    list($l, $r) = explode(" ", trim(fgets(STDIN)));
    echo $a[$r] - $a[$l-1];
    echo PHP_EOL;
  }

class PrimeNumber {

    public $prime = [];

    function createPrimeNumber($n){
      $sqrt = floor(sqrt($n));
      $lists = array_fill(2, $n-1, true);
      for ($i=2; $i<=$sqrt; $i++) {
        if (isset($lists[$i])) {
          for ($j=$i*2; $j<=$n; $j+=$i) {
            unset($lists[$j]);
          }
        }
      }
      $this->prime = array_keys($lists);
      return $this->prime;
    }

    function primeFactorization($value){
      if(count($this->prime) === 0){
        $this->createPrimeNumber($value);
      }
      $prime_count = count($this->prime);
      $ret=[];
      $sqrt=floor(sqrt($value));
      for($i=0;$i<$prime_count;$i++){
        // 平方根を超えた場合は残った値が素数
        if($sqrt < $this->prime[$i]){
          $ret[$value]=1;
          return $ret;
        }
        // 割り切れる間続ける
        while($value%$this->prime[$i]==0){
          if(!isset($ret[$this->prime[$i]])){
            $ret[$this->prime[$i]]=0;
          }
          $ret[$this->prime[$i]]++;
          $value=intdiv($value, $this->prime[$i]);
          if($value==1){
            return $ret;
          }
        }
      }
    }
  }

Measured memory_bytes: 48584
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ld double
#define mp make_pair
#define pb push_back
#define mod 1000000007
#define ff first
#define ss second
#define pll pair <ll,ll>
#define nl "\n"
ll dp[1002][1002];
int main()
{
	ios_base::sync_with_stdio(false);
	ll n,m,i,j,f;
	cin>>n>>m;
	string str[n+2];
	for(i=0;i<n;i++)
		cin>>str[i];
	dp[0][0]=1;
	f=0;
	for(i=1;i<m;i++)
	{
		if(str[0][i]=='#')f=1;
		if(!f)dp[0][i]=1;
	}
	f=0;
	for(i=1;i<n;i++)
	{
		if(str[i][0]=='#')f=1;
		if(!f)dp[i][0]=1;
	}
	for(i=1;i<n;i++)
	{
		for(j=1;j<m;j++)
		{
			if(str[i][j]=='#')continue;
			if(str[i-1][j]=='.')dp[i][j]=(dp[i-1][j]+dp[i][j])%mod;
			if(str[i][j-1]=='.')dp[i][j]=(dp[i][j-1]+dp[i][j])%mod;
		}
	}
	cout<<dp[n-1][m-1]<<nl;
	return 0;
}

Measured memory_bytes: 9088
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1];
        int[] b = new int[n+1];
        long sum = 0;
        for (int i = 0; i <= n; i++) {
            a[i] = sc.nextInt();
            sum += a[i];
        }
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            if (a[i] < b[i]) {
                b[i] -= a[i];
                a[i] = 0;
                
                if (a[i+1] < b[i]) {
                    a[i+1] = 0;
                } else {
                    a[i+1] -= b[i];
                }
            } else {
                a[i] -= b[i];
            }
        }
        
        long now = 0;
        for (int i = 0; i <= n; i++) {
            now += a[i];
        }
        
        System.out.println(sum - now);
    }
}


Measured memory_bytes: 74524
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) //[l, r)
#define rep(i,n) REP(i,0,n)           //[0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showslr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl //[l, r)

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

inline void io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}

void _DEBUG(){cerr<<endl;}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<",";_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<endl;out(b...);}

void RESIZE(int sz){}
template<class H,class... T> void RESIZE(int sz,H &a,T&... b){
    a.resize(sz);
    RESIZE(sz,b...);
}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

int n;
vi x,y,h;

signed main(){
    io();

    in(n);
    RESIZE(n,x,y,h);
    rep(i,n){
        in(x[i],y[i],h[i]);
    }
    rep(j,101){
        rep(i,101){
            bool f=true;
            int htmp=-1;
            rep(k,n){
                if(h[k]>0){
                    int dx=abs(i-x[k]),dy=abs(j-y[k]);
                    htmp=h[k]+dx+dy;
                    break;
                }
            }
            rep(k,n){
                int dx=abs(i-x[k]),dy=abs(j-y[k]);
                if(htmp-dx-dy<0){
                    if(h[k]!=0){
                        f=false;
                        break;
                    }
                }else{
                    if(htmp!=h[k]+dx+dy){
                        f=false;
                        break;
                    }
                }
            }
            if(f){
                printf("%lld %lld %lld\n",i,j,htmp);
                return 0;
            }
        }
    }

    return 1;
}


Measured memory_bytes: 256
def prime_factorize(n):
    a = [1]
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    a = list(set(a))
    return a

def main():
    a,b = list(map(int,input().split()))
    prime_a = prime_factorize(a)
    prime_b = prime_factorize(b)
    cnt = 0
    for i in prime_a:
        for j in prime_b:
            if i == j:
                cnt+=1
    print(cnt)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
#include<iostream>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<algorithm>
#include <vector>
using namespace std;

int main(){
    string s;cin>>s;
    int count=(1<<20);
    for (char i='a';i<'z'+1;i++){
        int now=0;
        int m=0;
        for(int j=0;j<s.size();j++){
            if(s[j]==i){
                now=0;
            }

            else {
                now+=1;
                m=max(now,m);
                }
            }
    count=min(m,count);
    }
    
cout<<count<<endl;
}


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

#define REP(i,n) for(ll i=0;i<n;++i)
#define RREP(i,n) for(ll i=n-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<n;++i)
#define RFOR(i,m,n) for(ll i=n-1;i>=m;--i)
#define ALL(v) (v).begin(),(v).end()
#define PB(a) push_back(a)
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(i, (v).size()) { cout << v[i]; if (i != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)(?´????????`)///
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vvi v(n,vi(n));
	REP(i, n)REP(j, n)cin >> v[i][j];
	ll ans = 0;
	REP(i, n) {
		FOR(j,i, n) {
			ans += min(v[i][j], v[j][i]);
		}
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
  int n, k;
  cin >> n >> k;
  int h[n];
  int c = 0;
  for (int i = 0; i < n; i++) {
    cin >> h[i];
    if (k <= h[i]) {
      c++;
    }
  }
  cout << c;
}

Measured memory_bytes: 640
#define r return
#define a (int u,int v,int x,int y,char m,int c)
i,j,n,f[6];w[8]={1,1,0,-1,-1,-1,0,1};h[8]={0,1,1,1,0,-1,-1,-1};char t[10][10],g[2]={'o','x'};l a{if(t[x][y]=='.'||t[x][y]=='0')r 0;if(t[x][y]==m)r c;r l(u,v,x+u,y+v,m,c+1);}s a{int k,d;d=0;if(t[x][y]!='.')r 0;for(k=0;k<8;k++)d+=l(w[k],h[k],x+w[k],y+h[k],m,0);r d;}p a{if(t[x][y]=='0'||t[x][y]=='.')r 0;if(t[x][y]==m)r 1;if(p(u,v,x+u,y+v,m,0)){t[x][y]=m;r 1;}else r 0;}o a{int k;t[x][y]=m;for(k=0;k<8;k++)p(w[k],h[k],x+w[k],y+h[k],m,0);r 0;}main(){for(i=0;i<10;)t[0][i]=t[9][i++]='0';for(i=1;i<9;t[i][0]=t[i++][9]='0')scanf("%s",&t[i][1]);for(n=f[1]=-1;f[n]=-1;n=(n+1)%2){for(i=n?8:1;n?i>-1:i<9;n?i--:i++)for(j=n?8:1;n?j>-1:j<9;n?j--:j++)f[n]<s(0,0,i,j,g[n],0)?f[2+n]=i,f[4+n]=j,f[n]=s(0,0,i,j,g[n],0):0;f[n]!=0?o(0,0,f[2+n],f[4+n],g[n],0):0;if(f[0]==0&&f[1]==0)break;}for(i=1;i<9;i++,puts(""))for(j=1;j<9;j++)printf("%c",t[i][j]);r 0;}

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

using namespace std;

#define pii pair<int, int>
#define pll pair<ll, ll>

#define pb push_back
#define eb emplace_back
#define mp make_pair

#define fi first
#define se second

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int inf = (int)1e9 + 7;
const int maxn = (int)6e5 + 7;
const int lmaxn = (int)6e6 + 7;
const ll linf = (ll)1e16 + 7;

const ld eps = ld(1e-11);

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

ll gcd(ll a, ll b){
    while(b) a %= b, swap(a, b);
    return a | b;
}

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

ll n;

int main(){
    scanf("%lld", &n);
    printf("%lld", n * (n + 1) / 2);
    return 0;
}



Measured memory_bytes: 256
import java.io.IOException;
import java.util.NoSuchElementException;

import java.io.InputStream;

import java.io.PrintWriter;

@SuppressWarnings("unchecked")
public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);

        final int MAX_N = 100000;

        final int N = nextInt();
        final long K = nextLong();

        long[] A = new long[MAX_N];

        for (int i = 0; i < N; i++)
            A[nextInt() - 1] += nextLong();

        long k = 0;
        int ans = 0;

        for (int i = 0; i < MAX_N; i++) {
            k += A[i];
            if (K <= k) {
                ans = i + 1;
                break;
            }
        }

        out.println(ans);

        out.flush();
    }

    // FastScanner start
    static final InputStream in = System.in;
    static final byte[] buffer = new byte[1024];
    static int ptr = 0;
    static int buflen = 0;
    static boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    static int readByte() {
        if (hasNextByte()) return buffer[ptr++];
        else return -1;
    }
    static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }
    static boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
        return hasNextByte();
    }
    static String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    static long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if(b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    static int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }
    static double nextDouble() {
        return Double.parseDouble(next());
    }
    // FastScanner end
}


Measured memory_bytes: 22228
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(),b= sc.nextInt();
        int ans = 0;
        for(int i = a;i<=b;i++){
            int s= i%10, t = i/10000%10;
            int u = i/10%10,v=i/1000%10;
            if(s==t&&u==v){
                ans ++;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 24148
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
"""
10       9       8          0+10+9
10   7   9   6   8   5      +9+8+8
10 4 7 3 9 2 6 1 8 0 5 -1   +7+7+6+6  +5+5
                            +4+4+3+3+2+2+1+1+..."""
ans=A[0]

if N>=3:
    ans+=A[1]
if N>=4:
    ans+=A[1]
if N>=5:
    ans+=A[2]
if N>=6:
    ans+=A[2]
if N>=7:
    if N%2:
        ans+=sum(A[3:3+(N+1-6)//2])*2
        ans-=A[3+(N-6)//2]
    else:
        ans+=sum(A[3:3+(N-6)//2])*2
print(ans)

Measured memory_bytes: 30996
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
	int a[10000],n,i,j,t,c=0,min;	cin>>n;
	for(i=0;i<n;i++)cin>>a[i];
	for(i=0;i<n;i++){
		min=i;
		for(j=i;j<n;j++){
			if(a[j]<a[min])min=j;
		}
		if(i!=min){
			t=a[min];
			a[min]=a[i];
			a[i]=t;
			c++;
		}
	}
		for(i=0;i<n;i++){
			if(i)cout<<" ";
			cout<<a[i];
		}
		cout<<endl<<c<<endl;
			return 0;
		
}

Measured memory_bytes: 1172
n=int(input())
xy=[list(map(int,input().split())) for i in range(n)]

d=0
for i in range(n):
    for j in range(n):
        d+=((xy[i][0]-xy[j][0])**2+(xy[i][1]-xy[j][1])**2)**0.5
print(d/n)



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


int main(){
	int N;
	scanf("%d",&N);
	
	
	int number = N % 10;
	
	int NUMBER = (N-number)  %100;
	
	int BUN = (N-NUMBER-number);
	
	if(number != 7 && NUMBER !=70 && BUN != 700) {
		printf("No");
		return 0;
	}
	printf("Yes");
	
	
	
	return 0;
	
}

Measured memory_bytes: 1732
n,m,x = map(int,input().split())

A = [[] for _ in range(n)]
c = [0] * n

for i in range(n):
    c_as = list(map(int, input().split()))
    c[i], A[i] = c_as[0], c_as[1:]

INF = 10**9
ans = INF

for s in range(0,1 << n): #2進数
    smart = [0] * m
    cost_sum = 0
    for i in range(n):
        if (s >> i) % 2 == 0: continue
        cost_sum += c[i]
        for j in range(m):
            smart[j] += A[i][j]
    ok = True
    for j in range(m):
        if smart[j] < x:
            ok = False
    if ok:
        ans = min(ans, cost_sum)

if ans == INF:
    ans = -1

print(ans)

Measured memory_bytes: 9256
#include<bits/stdc++.h>
using namespace std;
 
#define MOD 998244353
template<typename ty1,typename ty2>
inline int add(ty1 x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x += y; return x < MOD ? x : x - MOD;
}
template<typename ty1,typename ty2>
inline void addto(ty1 &x, ty2 y) {
		  if(y>=MOD)y%=MOD;
		  if(x>=MOD)x%=MOD;
	      x += y; if (x >= MOD) x -= MOD;
}
template<typename ty1,typename ty2>
inline int sub(ty1 x, ty2 y) {
		if(y>=MOD)y%=MOD;
		 if(x>=MOD)x%=MOD;
        x -= y; return x < 0 ? x + MOD : x;
}
template<typename ty1,typename ty2>
inline void subto(ty1 &x, ty2 y) {
	if(y>=MOD)y%=MOD;
	if(x>=MOD)x%=MOD;
    x -= y; if (x < 0) x += MOD;
}
template<typename ty1,typename ty2>
inline int mul(ty1 x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        return 1ll * x * y % MOD;
}
template<typename ty1,typename ty2>
void multo(ty1 &x, ty2 y) {
        if(y>=MOD)y%=MOD;
		if(x>=MOD)x%=MOD;
        x=1ll * x * y % MOD;
}
 
 
long long int ppow(long long int i, long long int j){
		long long int res = 1LL;
		while (j){
			if ((j & 1LL)){
				res *= i;
				if (res >= MOD){
					res %= MOD;
				}
			}
			j >>= 1;
			i *= i;
			if (i >= MOD){
				i %= MOD;
			}
		}
		return res;
	}
class Combination{
	
public:
	vector<long long int> k;
	vector<long long int> r;
	void resize(int N){
		k.resize(N + 2);
		r.resize(N + 2);
		k[0] = 1;
		for (int i = 1; i < N+2; i++){
			k[i] = k[i - 1];
			k[i] *= i;
			if (k[i] >= MOD)k[i] %= MOD;
		}
		long long int al = k[k.size() - 1];
		long long int iv = ppow(k[k.size() - 1],MOD-2);
		r[k.size() - 1] = iv;
		for (int i = (int)(r.size()) - 2; i >= 0; i--){
			r[i] = r[i + 1] * (i + 1);
			if (r[i] >= MOD){
				r[i] %= MOD;
			}
		}
	}
	long long int C(int a, int b){
		if (a < b)return 0;
		long long int up = k[a];
		long long int dw = r[b] * r[a - b];
		dw %= MOD;
		up *= dw;
		up %= MOD;
		return up;
	}
	long long int H(int a, int b){
		return C(a + b - 1, b);
	}
	long long int catalan_number(int n){
		return (C(2 * n, n) + MOD - C(2 * n, n - 1)) % MOD;
	}
};
Combination C;

#define MAX 302

int n;
vector<int> v;

int dp[MAX][MAX*MAX][4];
int im[MAX];


int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int a;
		scanf("%d",&a);
		v.push_back(a);
	}
	//v[0]<=v[1]<=v[2]
	//v[0]+v[1]>v[2]
	for(int i=0;i<n;i++){
		im[i]+=v[i];
		if(i)im[i]+=im[i-1];
	}
	dp[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=300*i;j++){
			for(int k=0;k<4;k++){
				if(dp[i][j][k]==0)continue;
				//choose
				addto(dp[i+1][j+v[i]][k],dp[i][j][k]);
				//discard
				addto(dp[i+1][j][k|1],dp[i][j][k]);
				addto(dp[i+1][j][k|2],dp[i][j][k]);
			}
		}
	}
	int ans=0;
	int overall=0;
	for(int j=(im[n-1]+1)/2;j<=300*n;j++){
		addto(ans,mul(3,dp[n][j][3]));
	}
	for(int j=1;j<=300*n;j++){
		addto(overall,dp[n][j][3]);
	}
	subto(overall,ans);
	printf("%d\n",overall);
	return 0;
}


Measured memory_bytes: 428288
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n, m = MI()
    xx = set([0])
    yy = set([0])
    vl = []
    hl = []
    for _ in range(n):
        a, b, c = MI()
        xx.add(a)
        xx.add(b)
        yy.add(c)
        vl.append((a, b, c))
    for _ in range(m):
        a, b, c = MI()
        xx.add(a)
        yy.add(b)
        yy.add(c)
        hl.append((b, c, a))

    dex = list(sorted(xx))
    dey = list(sorted(yy))
    cox = {x: i for i, x in enumerate(dex)}
    coy = {x: i for i, x in enumerate(dey)}
    h = len(dex)
    w = len(dey)

    vlt=[[1]*w for _ in range(h)]
    for x0, x1, y in vl:
        j = coy[y]
        for i in range(cox[x0], cox[x1]):
            vlt[i][j]=0

    hlt=[[1]*w for _ in range(h)]
    for y0, y1, x in hl:
        i = cox[x]
        for j in range(coy[y0], coy[y1]):
            hlt[i][j]=0
    #p2D(vlt)
    #print()
    #p2D(hlt)

    tt = [[False] * w for _ in range(h)]

    def inf():
        print("INF")
        exit()

    def move(ni, nj):
        if tt[ni][nj]: return
        tt[ni][nj] = True
        stack.append((ni, nj))

    si, sj = cox[0], coy[0]
    if si==h-1 or sj==w-1:inf()
    stack = [(si, sj)]
    tt[si][sj] = True
    while stack:
        i, j = stack.pop()

        ni, nj = i, j - 1
        if vlt[i][j]:
            if nj == -1: inf()
            move(ni, nj)

        ni, nj = i, j + 1
        if vlt[ni][nj]:
            if nj == w - 1: inf()
            move(ni, nj)

        ni, nj = i - 1, j
        if hlt[i][j]:
            if ni == -1: inf()
            move(ni, nj)

        ni, nj = i + 1, j
        if hlt[ni][nj]:
            if ni == h - 1: inf()
            move(ni, nj)
    #p2D(tt)

    ans = 0
    for i in range(h - 1):
        for j in range(w - 1):
            if tt[i][j]: ans += (dex[i + 1] - dex[i]) * (dey[j + 1] - dey[j])
    print(ans)

main()


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

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int h, w, a, b;
    cin >> h >> w >> a >> b;

    auto ans = initVec2<int>(h, w);
    rep(i, b){
        rep(j, a){
            ans[i][j] = 1;
        }
    }
    for(int i = b; i < h; i++){
        for(int j = a; j < w; j++){
            ans[i][j] = 1;
        }
    }

    rep(i, h){
        rep(j, w){
            cout << ans[i][j];
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 9088
#include <cstdio>
#include <iostream>
#include <algorithm>
#define N 100010
#define ll long long
using namespace std;
ll n,m,cnt,a[N],f[N],Q[N],b[N];
void work(ll x,ll y)
{
	ll p=upper_bound(Q,Q+cnt+1,x)-Q-1;
	if (!p) b[1]+=y,b[x+1]-=y; else f[p]+=y*(x/Q[p]),work(x%Q[p],y);
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for (ll i=1;i<=m;i++) scanf("%lld",&a[i]);
	if (!m){ for (ll i=1;i<=n;i++) printf("1\n"); return 0; }
	Q[++cnt]=a[m]; for (ll i=m-1;i;i--) if (a[i]<Q[cnt]) Q[++cnt]=a[i];
	if (n<Q[cnt]) Q[++cnt]=n; 
	reverse(Q+1,Q+cnt+1),f[cnt]=1;
	for (ll i=cnt;i>1;i--) f[i-1]+=f[i]*(Q[i]/Q[i-1]),work(Q[i]%Q[i-1],f[i]);
	for (ll i=1;i<=n;i++) b[i]+=b[i-1];
	for (ll i=1;i<=Q[1];i++) b[i]+=f[1];
	for (ll i=1;i<=n;i++) printf("%lld\n",b[i]);
}

Measured memory_bytes: 4864
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define int long long int

signed main(){
    int n;
    cin >> n;
    int p[n];
    int count = 1;
    for(int i=0;i<n;i++){
        cin >> p[i];
    }
    int min_val = p[0];
    for(int i=1;i<n;i++){
        if(p[i] <= min_val){
            count++;
            min_val = min(min_val,p[i]);
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF 1000000000000000
signed main(){
  int N,M,S,T; cin>>N>>M>>S>>T;
  vector<vector<pii>> A(N),B(N);
  rep(i,0,M){
    int a,b,c,d; cin>>a>>b>>c>>d;
    A[a-1].pb(mp(b-1,c));
    A[b-1].pb(mp(a-1,c));
    B[a-1].pb(mp(b-1,d));
    B[b-1].pb(mp(a-1,d));
  }
  S--;
  T--;
  vi F(N,INF),G(N,INF);
  priority_queue<pii,vector<pii>,greater<pii>> Q;
  Q.push(mp(S,0));
  F[S]=0;
  while(Q.size()>0){
    int X=Q.top().first,Y=Q.top().second;
    Q.pop();
    rep(i,0,A[X].size()){
      int P=A[X][i].first,R=Y+A[X][i].second;
      if(F[P]>R){
        F[P]=R;
        Q.push(mp(P,R));
      }
    }
  }
  Q.push(mp(T,0));
  G[T]=0;
  while(Q.size()>0){
    int X=Q.top().first,Y=Q.top().second;
    Q.pop();
    rep(i,0,B[X].size()){
      int P=B[X][i].first,R=Y+B[X][i].second;
      if(G[P]>R){
        G[P]=R;
        Q.push(mp(P,R));
      }
    }
  }
  vi dp(N);
  rep(i,0,N) dp[i]=F[i]+G[i];
  REP(i,2,N) dp[N-i]=min(dp[N-i],dp[N-i+1]);
  rep(i,0,N){
    cout<<max(0ll,INF-dp[i])<<endl;
  }
  }



Measured memory_bytes: 21488
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(begin, i, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    string S;
    cin >> S;
    ll day = 0, ans = 0;
    rep(0, i, 3)
    {
        if (S.at(i) == 'R')
        {
            day++;
            ans = max(ans, day);
        }
        else
        {
            ans = max(ans, day);
            day = 0;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3576
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;


int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> candle(n);
	for (int i = 0; i < n; i++) {
		cin >> candle[i];
	}
	sort(candle.begin(), candle.end());
	int ans = min(abs(candle[0]),abs(candle[k-1])) + abs(candle[0] - candle[k-1]);
	for (int i = 0; i <= n - k; i++) {
		int temp = min(abs(candle[i]), abs(candle[i + k - 1])) + abs(candle[i] - candle[i + k - 1]);
		if (temp < ans) {
			ans = temp;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
using namespace std;

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

    if (k == 1) cout << 0 << endl;
    else cout << n - k << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()
#------------------------------
#########タイムオーバー########
#------------------------------
# minimum = 300000
# for i in range(N):
    # leftWestNum = S[:i].count('W')
    # rightEstNum = S[i+1:N].count('E')
    # tmpMin = leftWestNum + rightEstNum
    # if tmpMin < minimum:
        # minimum = tmpMin
# print(minimum)

minimum = 3000000
numEast = [0] * (N+1)
numWest = [0] * (N+1)
for i in range(N):
    if S[i] == 'E':
        numEast[i+1] = numEast[i] + 1
        numWest[i+1] = numWest[i]
    else:
        numEast[i+1] = numEast[i]
        numWest[i+1] = numWest[i] + 1

for i in range(N):
    tmpMin = numWest[i] + (numEast[N]-numEast[i+1])
    if tmpMin < minimum:
        minimum = tmpMin

print(minimum)

Measured memory_bytes: 17636
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
'''
def main():
    N, M = LI()
    digits = [-1 for _ in range(N)]
    for _ in range(M):
        s, c = LI()
        if N > 1 and s == 1 and c == 0:
            print("-1")
            return
        if digits[s-1] == -1:
            digits[s-1] = c
        else:
            if digits[s-1] != c:
                print("-1")
                return 
    for i, d in enumerate(digits):
        if N == 1 and i == 0 and d == 0:
            print(0)
            return
        if i == 0 and d == 0:
            print("-1")
            return 
        if i > 0 and d == -1:
            digits[i] = 0
        if i == 0 and d == -1:
            digits[i] = 1

    print(''.join([str(x) for x in digits]))
'''
def main():
    N, M = LI()
    q = []
    for _ in range(M):
        s, c = LI()
        q.append((s, str(c)))
    for x in range(0, 1000):
        flag = True
        x = str(x)
        if len(x) < N:
            continue
        for (s, c) in q:
            s -= 1
            if c != x[s]:
                flag = False
            
        if flag:
            print(x)
            return
    print("-1")

main()



Measured memory_bytes: 5436