akhauriyash/Code-Regression huggingface dataset:
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
// ============ template finished ============
constexpr int SIZE = 26;
using ALPHA = bitset<SIZE>;

vector<ALPHA> parse_bits(const string& s) {
    const int len = s.size();
    vector<ALPHA> res(len + 1, 0);
    rep(i, len) {
        int idx = s[i] - 'a';
        ALPHA buf(1 << idx);
        res[i + 1] = res[i] ^ buf;
    }
    return res;
}

unordered_map<ALPHA, set<int>> compress(const vector<ALPHA>& bits) {
    unordered_map<ALPHA, set<int>> mp;
    rep(i, bits.size())mp[bits[i]].insert(i);
    return mp;
}

unordered_set<ALPHA> make_nexts(ALPHA bit) {
    unordered_set<ALPHA> st;
    rep(i, SIZE) {
        ALPHA buf(1 << i);
        bit ^= buf;
        st.insert(bit);
        bit ^= buf;
    }
    return st;
}

void even_palindrome_transition(
    vector<int>& dp,
    const unordered_map<ALPHA, set<int>>& mp,
    const vector<ALPHA>& bits,
    const int i
) {
    const auto& st = mp.at(bits[i]);
    const auto itr = st.upper_bound(i);
    if (itr != st.end()) {
        int idx = *itr;
        dp[idx] = min(dp[idx], dp[i] + 0);
    }
}

void odd_palindrome_transition(
    vector<int>& dp,
    const unordered_map<ALPHA, set<int>>& mp,
    const vector<ALPHA>& bits,
    const int i
) {
    const auto nexts = make_nexts(bits[i]);
    for (auto next : nexts) {
        if (mp.find(next) == mp.end())continue;
        const auto& st = mp.at(next);
        const auto itr = st.lower_bound(i);
        if (itr != st.end()) {
            int idx = *itr;
            dp[idx] = min(dp[idx], dp[i] + 1);
        }
    }
}

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

    auto bits = parse_bits(s);
    auto mp = compress(bits);
    const int len = s.size();
    vector<int> dp(len + 1, INF);

    dp[0] = 0;
    rep(i, len) {
        even_palindrome_transition(dp, mp, bits, i);
        odd_palindrome_transition(dp, mp, bits, i);
    }
    int res = dp.back();
    cout << (res == 0 ? 1 : res) << endl;
    return 0;
}


Measured memory_bytes: 32708
import java.util.Scanner;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int W = sc.nextInt();
        int H = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.print((double)W*H/2);
        System.out.print(" ");
        if(W%2==0&&H%2==0 && x == W/2 && y == H/2){
            System.out.print(1);
        }else{
            System.out.print(0);
        }

    }

}


Measured memory_bytes: 25172
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

int main() {
  int n;
  string s;
  cin >> n >> s;
  if (n % 2) {
    cout << "No" << endl;
    return 0;
  }
  string t = s.substr(n / 2);
  if (t + t == s) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   for(int i=0;i<(n);++i)
#define SORT(c)    sort((c).begin(),(c).end())
#define CLR(a)     memset((&a), 0 ,sizeof(a))//clear memory
#define dump(x)    cerr << #x << " = " << (x) << endl;//debug
#define debug(x)   cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define EPS        1e-10//sample:if((double)>=(double)+EPS)
//cin,cout release
//std::cin.tie(0);
//ios::sync_with_stdio(false);

using namespace std;

int n,v[100+1][100+1]={},d[1000]={},color[1000]={};
int q[1000]={},head=0,tail=0;
void bfs(int s){
  rep(i,n){
    if(v[s][i]==0&&s!=i){
      color[s]=0;
      d[i]=INT_MAX;
    }
  }
  color[s]=1;
  d[s]=0;
  head=tail=0;
  q[tail++]=s;
  while(head!=tail){
    int u=q[head++];
    rep(i,n){
      if(v[u][i]==0)continue;
      if(color[i]==0){
	color[i]=1;
	d[i]=d[u]+1;
	q[tail++]=i;
      }
    }
    color[u]=2;
  }
}
int main(){
  cin>>n;
  int u,k,in;
  rep(i,n){
    cin>>u>>k;
    rep(j,k){
      cin>>in;
      v[u-1][in-1]=1;
    }
  }
  //rep(i,n)
  bfs(0);
  rep(i,n){
    cout<<i+1<<" ";
    if(d[i]==INT_MAX)cout<<-1;
    else cout<<d[i];
    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3128
#include<bits/stdc++.h>
#include<string>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define forN(i, n) for(int i = 0; i <n ; ++i)
#define endl "\n"
typedef long long ll;
using namespace  std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const int N = 1e5 + 5;
ll h , n ,A[N];


int main(){
    fastIO;
    cin>>h>>n;
    for(int i = 0 ; i<n ; i++){
        cin>>A[i];
        h-=A[i];
    }
    if(h<=0){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }

}


Measured memory_bytes: 4360
import math
from collections import defaultdict

def main():
    N = int(input())
    Al = [int(x) for x in input().split()]
    center = int(N/2)
    cnt = 0
    m = defaultdict(int)
    for i in range(N):
        m[i+Al[i]] += 1
        cnt += m[i-Al[i]]
    print(cnt)

if __name__ == '__main__':
    main()

Measured memory_bytes: 61104
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
q = 0
c = 0
for n in range(N):
  A = list(map(int,input().split()))
  q = 0
  for m in range(M):
    q += A[m]*B[m]
    if m+1 == M and q+C > 0:
      c +=1
print(c)
     

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

using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VD = vector<double>;
using VVD = vector<VD>;
using VS = vector<string>;
using PII = pair<int, int>;
using VPII = vector<PII>;
using VL = vector<long long>;
using VVL = vector<VL>;

#define sz(var) (int)var.size()
#define REP(var, start, end) for(int var = start; var < (int)end; ++var)
#define CLEAR(var, with) memset(var, with, sizeof(var))
#define ALL(x) x.begin(), x.end()
#define LL long long
#define ULL unsigned long long
#define TIME cout << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
#ifndef ONLINE_JUDGE
	//freopen("tmp.in", "r", stdin);
//	freopen("tmp.out", "w", stderr);
#endif
    int a, b; char op;
    scanf("%d %c %d", &a, &op, &b);

    cout << (op == '+' ? a + b : a - b) << endl;

	return 0;
}

Measured memory_bytes: 256
s=input()
ans=0
if s[0]=='A':
  ans+=1
  s=s[1:]
if 'C' in s[1:-1]:
  ans+=1
  for i in range(1,len(s)-1):
    if s[i]=='C':
      s=s[:i]+s[i+1:]
      break
count=0
for i in range(len(s)):
  if s[i] in "ABCDEFGHIJKLMNOPQRSTUVWXYZ":
    count+=1
if count==0:
  ans+=1
print("AC" if ans==3 else "WA")

Measured memory_bytes: 3064
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 
          53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
          109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167,
          173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
          233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
          293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359,
          367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431,
          433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491,
          499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 
          577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 
          643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 
          719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 
          797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 
          863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
          947, 953, 967, 971, 977, 983, 991, 997]         

def nCr(n,r):
  N = 1
  R = 1
  for m in range(n-r,n+1):
    N *= m
    
  for m in range(2,r+1):
    R *= m
    
  return N//R
    

n = int(input())
primes = [p for p in primes if p <= n]
numpow = []
for p in primes:
  i = 1
  tmp = 0
  divisor = p
  while divisor <= n:
    tmp += (n // divisor)
    i += 1
    divisor = p**i
  numpow.append(tmp)

import math    
numpow = [i+1 for i in numpow]
y = math.prod(numpow)
print(y % (10**9+7))
  

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

bool dpX[3000][8010], dpY[3000][8010];

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

    int x, y;
    cin >> x >> y;

    int initX = 0,
        initY = 0;
    
    // SSSS...Tの分だけ動かす
    int idx = 0;
    while (idx < s.size() and s[idx] == 'F') {
        initX++;
        idx++;
    }

    vector<int> xmoves, ymoves;
    int xsum = 0,
        ysum = 0,
        turn = 1;
    while (idx < s.size()) {
        // idxはTを指している
        int nidx = idx + 1; 
        while (nidx < s.size() and s[nidx] == 'F') {
            nidx++;
        }
        int len = nidx - idx - 1;
        if (len > 0) {
            if (turn == 0) {
                xmoves.push_back(len);
                xsum += len;
            } else {
                ymoves.push_back(len);
                ysum += len;
            }
        }
        turn ^= 1;

        idx = nidx;
    }

    dpX[0][0] = dpY[0][0] = true;
    for (int i = 0; i < xmoves.size(); i++) {
        for (int x = 0; x <= s.size(); x++) {
            dpX[i + 1][x] |= dpX[i][x];
            dpX[i + 1][x + xmoves[i]] |= dpX[i][x];
        }
    }

    for (int i = 0; i < ymoves.size(); i++) {
        for (int y = 0; y <= s.size(); y++) {
            dpY[i + 1][y] |= dpY[i][y];
            dpY[i + 1][y + ymoves[i]] |= dpY[i][y];
        }
    }

    // aだけx軸正の方向に移動したとすると...initX + a - (xsum - a) = initX - xsum + 2a = x?を調べる
    // => 2a = x + xsum - initXを満たすaが存在するかどうかを調べる
    // cerr << "xsum: " << xsum << " initX: " << initX << endl;
    cerr << (x + xsum - initX) / 2 << endl;
    if ((x + xsum - initX) % 2) {
        cerr << "aaa" << endl;
        cout << "No" << endl;
        return 0;
    } else if (not dpX[xmoves.size()][(x + xsum - initX) / 2]) {
        cerr << "iii" << endl;
        cout << "No" << endl;
        return 0;
    }

    if ((y + ysum - initY) % 2) {
        cerr << "uuu" << endl;
        cout << "No" << endl;
        return 0;
    } else if (not dpY[ymoves.size()][(y + ysum - initY) / 2]) {
        cerr << "eee" << endl;
        cout << "No" << endl;
        return 0;
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 35072
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		while (true) {
			int r = sc.nextInt();
			int c = sc.nextInt();
			if ((r | c) == 0)
				break;
			System.out.println(r * c % 2 == 0 ? "yes" : "no");
		}
	}
}

Measured memory_bytes: 12000
#include<stdio.h>

int main(void)

{

int i ,j ,k ,l ,m=0 ,n ;



while(scanf("%d",&n) != EOF)

{

m=0 ;

for(i=0 ; i<10 ; i++)

{

for(j=0 ; j<10 ; j++)

{

for(k=0 ; k<10 ; k++)

{

for(l=0 ; l<10 ; l++)

{

if(i+j+k+l==n)m++;

}

}

}
}

printf("%d\n",m) ;

}

return 0 ;

}

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

int main() {
  int N,a;
  cin>>N;
  std::vector<int> v(100005);
  for(int i=0;i<N;i++){
    cin>>a;
    v[a]++;
    v[a+1]++;
    v[a+2]++;
  }
  int ans=0;
  for(int i=0;i<100005;i++)ans=max(ans,v[i]);
  cout<<ans<<endl;
}


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

int main(){
    string s;
    cin >> s;
    int leng = s.length();
    while(s[0] == 'B'||s[1] == 'B'){
    while(s[0] == 'B'){
        s.erase(0, 1);
        leng -= 1;
    }
    while(s[1] == 'B'){
        s.erase(0, 2);
        leng -= 2;
    }
    }   
    while(s.find("B") != string::npos){
        for(int i = 0;i < leng;i++){
            if(s[i] == 'B'){
                s.erase(i-1, 2);
                leng -= 2;
                break;
            }
            else{
                continue;
            }
        }
    }
    cout << s;    
}
    

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 1e4
	maxBufSize     = 1e6 + 7
)

var buf []byte = make([]byte, maxBufSize)
var sc = bufio.NewScanner(os.Stdin)

func init() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(buf, maxBufSize)
}

func main() {
	X := nextInt()
	for i := -200; i < 200; i++ {
		for j := -200; j < 200; j++ {
			A5 := i * i * i * i * i
			B5 := j * j * j * j * j
			if A5-B5 == X {
				fmt.Println(i, j)
				return
			}
		}
	}
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define  fi0 for(ll i=0;i<n;i++)
string s;
string strd(int n){
    string x;
    while(n){
        int d=n%10;
        x+=(d+'0');
        n/=10;
    }
    reverse(x.begin(),x.end());
    return x;
}
void digit()
{
    cin>>s;
    ll sum=0;
    for(int i=0;i<s.size();i++){
        char a=(char)s[i];
        int d=(int) a-'0';
        sum+=d;
    }
    if(sum%9==0)cout<<"Yes\n";
    else cout<<"No\n";
}
int main()
{
   ll n;
   cin>>n;
   ll cnt=0;
   ll a[n];
  fi0{
    cin>>a[i];
   }

   sort(a,a+n);
   ///fi0 cout<<a[i]<<' ';
   for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        for(int k=j+1;k<n;k++){
             if(a[i]!=a[j]&&a[j]!=a[k]){
                vector<ll>xxx;
                xxx.push_back(a[i]);
                xxx.push_back(a[j]);
                xxx.push_back(a[k]);
                sort(xxx.begin(),xxx.end());
                if(xxx[0]+xxx[1]>xxx[2])cnt++;
             }
        }
    }
   }
   cout<<cnt<<endl;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mp make_pair
using namespace std;
ll fi[1009][1009];
ll cnt[1000009],sum[1000009];
int main(){
	vector<ll> a,b;
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		ll x;
		cin>>x;
		a.pb(x);
	}
	for(int i=0;i<m;i++){
		ll x;
		cin>>x;
		b.pb(x);
	}
	sort(a.begin(),a.end());
	sort(b.begin(),b.end());
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			fi[i][j]=min(a[i],b[j]);
			cnt[fi[i][j]]++;
		}
	}
	for(int i=m*n;i>=0;i--){
		sum[i]=sum[i+1]+cnt[i];
	}
	ll ans = 1;
	ll ac=a.size()-1,bc=b.size()-1;
	for(int i=m*n;i>=1;i--){
		if(ac>=0 && bc>=0 && a[ac]==i && b[bc]==i){
			ans *= 1;
			ac--;
			bc--;
		}
		else if(ac>=0 && a[ac]==i){
			ans *= b.size()-bc-1;
			ans %= mod;
			ac--;
		}
		else if(bc>=0 && b[bc]==i){
			ans *= a.size()-ac-1;
			ans %= mod;
			bc--;
		}
		else{
			ans *= (a.size()-ac-1)*(b.size()-bc-1)-(m*n-i);
			ans %= mod;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 19072
#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> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const 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;
#define FI first
#define SE second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))


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


Measured memory_bytes: 256
#include <assert.h>
#include <limits>
#include <iostream>
#include <random>
#include <bitset>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <iterator>
#include <thread>
#include <stack>
#include <numeric>
#include <queue>
#include <unordered_set>
#include <set>
#include <sstream>
#include <iomanip>
#include <chrono>
#include <ctime>

using namespace std;

#define pv(x) printVector(x)
#define pvv(x) printVectorsOfVector(x)
#define f0(n) for(int i = 0; i < n; ++i)
#define f0e(n) for(int i = 0; i <= n; ++i)
#define f1(n) for(int i = 1; i < n; ++i)
#define f1e(n) for(int i = 1; i <= n; ++i)
#define eol cout<<endl

typedef vector<int> vi;
typedef vector<vector<int>> vvi;

template <class T>
void printVector(const vector<T>& v)
{
	for (T& i : v)
	{
		cout << i << " ";
	}
	cout << endl;
}

template <class T>
void printVectorsOfVector(const vector<vector<T>>& v)
{
	cout << " [ " << endl;
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << "  ";
		cout << " [ ";
		for (size_t j = 0; j < v[i].size(); j++)
		{
			cout << v[i][j];
			if (j != v[i].size() - 1)
				cout << " , ";
		}
		cout << " ] ";
		cout << endl;
	}
	cout << " [ ";
	cout << endl;
}

////////////////////////////////////////////////////////////////////
// Write your code here onwards...
////////////////////////////////////////////////////////////////////

static int __ = []() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cout.tie(nullptr);
  return 0;
}();

int main() {
  int N = 0;
  cin >> N;
	if (N % 1000 == 0)
		cout << 0;
	else
		cout << (N / 1000 + 1) * 1000 - N;
	return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

template<typename C> struct Flow {
	int V;
	C INF;
	struct E { int t, r; C c; };
	vector<vector<E>> g;
	vector<bool> used;
	
	Flow() { }
	Flow(int v, C inf) { init(v, inf); }
	void init(int v, C inf) {
		V = v;
		INF = inf;
		g.resize(V);
		used.resize(V);
	}
	
	void add(int f, int t, C c) {
		assert(inID(f, 0, V));
		assert(inID(t, 0, V));
		int gt = g[t].size();
		int gf = g[f].size();
		g[f].PB({ t, gt, c });
		g[t].PB({ f, gf, 0 });
	}
	
	C dfs(int f, int t, C c) {
		if(f == t) { return c; }
		used[f] = true;
		inc(i, g[f].size()) {
			E & e = g[f][i];
			if(used[e.t] || e.c <= 0) { continue; }
			C v = dfs(e.t, t, min(c, e.c));
			if(v > 0) {
				e.c -= v;
				g[e.t][e.r].c += v;
				return v;
			}
		}
		return 0;
	}
	
	C max_flow(int S, int T) {
		assert(inID(S, 0, V));
		assert(inID(T, 0, V));
		C ans = 0;
		while(true) {
			inc(i, V) { used[i] = false; }
			C f = dfs(S, T, INF);
			ans += f;
			if(f == 0) { break; }
		}
		return ans;
	}
};

// ----

int n, a[100], b[100], c[100], d[100];

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i] >> b[i]; }
	inc(i, n) { cin >> c[i] >> d[i]; }
	
	Flow<int> f(2 * n + 2, 1e4);
	int S = 2 * n + 0;
	int T = 2 * n + 1;
	
	inc(i, n) { f.add(S, i, 1); }
	inc(i, n) {
	inc(j, n) {
		f.add(i, n + j, (a[i] < c[j] && b[i] < d[j] ? 1 : 0));
	}
	}
	inc(j, n) { f.add(n + j, T, 1); }
	
	cout << f.max_flow(S, T) << endl;
	
	return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repi(i, a, b) for (int i = (a); i < int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = int;
using i64 = long long;
using f64 = double;
using vi32 = vector<i32>;
using vi64 = vector<i64>;
using vf64 = vector<f64>;
using vstr = vector<string>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int a, b, c;
  cin >> a >> b >> c;
  if (a == b && b == c) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
// これは前に見たのでわかる
// 太郎次郎とよぶより、先手後手といったほうがわかりやすいかも

// 状態は石の個数, O(K)
// dp配列にその状態での答えを保持
// 遷移は O(N)

#pragma region Header
#ifdef DEBUG
#include "debug.hpp"
#else
#define debug(...)
#define IFD(...)
#ifndef NDEBUG
#define NDEBUG
#endif
#endif
#include <utility>
#include <cstdint>
#include <cmath>
#include <cassert>
#include <vector>
#include <array>
#include <deque>
#include <queue>
#include <stack>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <string>
#include <functional>
#include <algorithm>
#include <numeric>
#include <stdexcept>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <boost/hana/functional/fix.hpp>
using boost::hana::fix;
using namespace std;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repd(i, n) for (int i = (n)-1; i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, b, a) for (int i = (b); i >= (a); --i)
template <typename T>
int SZ(T const &x)
{
    return static_cast<int>(x.size());
}
template <class T>
bool chmax(T &a, T const &b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class T>
bool chmin(T &a, T const &b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}
#pragma endregion

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);

    int n;
    cin >> n;
    int k;
    cin >> k;
    vector a_s(n, 0);
    rep(i, n) { cin >> a_s[i]; }

    // 先手が勝つか?
    vector dp(k + 1, false);
    FOR(i, 1, k)
    {
        for (int j = 0; j < n and a_s[j] <= i; ++j)
        {
            if (not dp[i - a_s[j]])
            {
                dp[i] = true;
                break;
            }
        }
    }
    cout << (dp[k] ? "First" : "Second") << '\n';

    return 0;
}


Measured memory_bytes: 3672
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using Graph = vector<vector<int>>;

int main()
{
    int N, M;
    cin >> N >> M;
    long long H[N];
    for (int i = 0; i < N; i++) cin >> H[i];

    Graph G(N);
    for (int i = 0; i < M; i++) {
        int from, to;
        cin >> from >> to;
        from = from - 1;
        to = to - 1;
        G[from].push_back(to);
        G[to].push_back(from);
    }

    int cnt = 0;
    for (int i = 0; i < N; i++) {
        vector<int> R = G[i];
        if (R.size() == 0) { cnt++; continue; }
        vector<long long> height;
        for (int j = 0; j < R.size(); j++) {
            height.push_back(H[R[j]]);
        }
        if (H[i] > *max_element(height.begin(), height.end())) cnt++;
    }

    cout << cnt;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define ll long long
#define pii pair<int,int>
#define all(x) begin(x), end(x)
#define loop(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b,c) for(int i=a; i<b; i+=c)
#define brep(i,a,b,c) for(int i=a; i>b; i-=c)
#define tc(t) int t; cin>>t; while(t--)
#define sz(v) int((v).size())
#define pb push_back

const int maxm = 1000000000 + 7;


using namespace std;


int main()
{

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int x;
	cin >> x;

	if (x <= 599) cout << 8 << endl;
	if (x > 599 && x <= 799)cout << 7 << endl;
	if (x > 799 && x <= 999) cout << 6 << endl;
	if (x > 999 && x <= 1199)cout << 5 << endl;
	if (x > 1199 && x <= 1399) cout << 4 << endl;
	if (x > 1399 && x <= 1599)cout << 3 << endl;
	if (x > 1599 && x <= 1799) cout << 2 << endl;
	if (x > 1799 && x <= 1999)cout << 1 << endl;


	return 0;




}

Measured memory_bytes: 3588
MOD = None
sum_e = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0)
sum_ie = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0)
class Convolution:

    # ROOT = 3
    def __init__(self, mod):
        global MOD
        MOD = mod
        # self.MOD = mod

    def __butterfly(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        # MOD = self.MOD

        for ph in range(1, h + 1):
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            now = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p] * now
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (l - r) % MOD
                now *= sum_e[(~s & -~s).bit_length() - 1]
                now %= MOD

    def __butterfly_inv(self, arr):
        n = len(arr)
        h = (n - 1).bit_length()
        # MOD = self.MOD

        for ph in range(1, h + 1)[::-1]:
            w = 1 << (ph - 1)
            p = 1 << (h - ph)
            inow = 1
            for s in range(w):
                offset = s << (h - ph + 1)
                for i in range(p):
                    l = arr[i + offset]
                    r = arr[i + offset + p]
                    arr[i + offset] = (l + r) % MOD
                    arr[i + offset + p] = (MOD + l - r) * inow % MOD
                inow *= sum_ie[(~s & -~s).bit_length() - 1]
                inow %= MOD

    def __call__(self, a, b):
        n = len(a)
        m = len(b)
        # MOD = self.MOD
        if not n or not m: return []
        if min(n, m) <= 50:
            if n < m:
                n, m = m, n
                a, b = b, a
            res = [0] * (n + m - 1)
            for i in range(n):
                for j in range(m):
                    res[i + j] += a[i] * b[j]
                    res[i + j] %= MOD
            return res
        z = 1 << (n + m - 2).bit_length()
        a += [0] * (z - n)
        b += [0] * (z - m)
        self.__butterfly(a)
        self.__butterfly(b)
        for i in range(z):
            a[i] *= b[i]
            a[i] %= MOD
        self.__butterfly_inv(a)
        a = a[:n + m - 1]
        iz = pow(z, MOD - 2, MOD)
        for i in range(n + m - 1):
            a[i] *= iz
            a[i] %= MOD
        return a




def atcoder_practice2_f():
    import sys
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    A = [int(x) for x in input().split()]
    B = [int(x) for x in input().split()]

    convolution = Convolution(998244353)
    print(*convolution(A, B))


if __name__ == "__main__":
    atcoder_practice2_f()


Measured memory_bytes: 197240
/*
  Fuad Ashraful Islam
  University of Asia Pacific,Bangladesh
  Date:11th May 2020
  Category:BinarySearch + DP
  ToDo:
 */
#include<bits/stdc++.h>
#define dbg(x) cerr <<__LINE__<<" where "<< #x << " = " << x << endl
#define all(x) (x).begin(),(x).end()

using namespace std;
template <class T> inline void read(T &res)
{
    res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    if (bo) res = ~res + 1;
}
const int N=2e5+5;
typedef long long ll;
ll len,_,n,d,k,m,l,c,cs=1;
const ll mod=998244353;
ll  fact[N];

ll ModInverse(ll num,ll pwr)
{
  if(!pwr)return 1LL;
  if(pwr&1)return (num*ModInverse(num,pwr-1))%mod;
  ll r1=ModInverse(num,pwr>>1);
  return (r1*r1)%mod;
} /// end func

void HalfDead() 
{
  fact[0]=1;
  for(ll i=1;i<N;++i)
  {
    fact[i]=(fact[i-1]*i)%mod;
  }
  ll ans=0;
  read(n); read(m); read(k);
  ll a=n-1;
  for(ll p=0;p<=k;++p)
  {
    ll r1=fact[a];
    ll r2=(fact[p]*fact[a-p])%mod;
    r2=ModInverse(r2,mod-2);
    r1=(r1*r2)%mod;
    r1=(r1*m)%mod;
    r2=ModInverse(m-1,n-p-1);
    r1=(r1*r2)%mod;

    ans+=(r1);
    ans%=mod;
  }
  cout<<ans<<"\n";
}
int main()
{
  HalfDead();
  return 0;
}


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

int main()
{
  int n, m, c, tmp;
  int a[100][100];
  int b[100];
  
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      cin >> a[i][j];
  for (int i = 0; i < m; i++) cin >> b[i];

  for (int i = 0; i < n; i++) {
    c = 0;
    for (int j = 0; j < m; j++) c += a[i][j] * b[j];
    cout << c << endl;
  }
  return 0;
}


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
int t;
long long a,b,c,d,gg,tmp,x;
void solve(){
	cin>>a>>b>>c>>d;
	if(b>a){
		cout<<"No"<<endl;
		return;
	}
	if(b>d){
		cout<<"No"<<endl;
		return;
	}
	gg=__gcd(b,d);
	tmp=(c-b+1)/gg;
	if((c-b+1)<0)
		tmp--;
	x=tmp*gg+a%gg;
	if(x<(c-b+1))
		x+=gg;
	if(x>=0) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>t;
	while(t--)
		solve();
	return 0;
}


Measured memory_bytes: 3644
import copy
n=int(input())
x=list(input())
b=[]
for i in range(2**18):
  b.append(format(i,'0'+str(18)+'b'))
  if i>n+1:
    break
ct=[0]*(n+1)
for i in range(1,n):
  ct1=0
  for j in range(len(b[i])):
    if b[i][j]=='1':
      ct1+=1
  ct[i]=i%ct1

CT=0
for i in range(n):
  if x[i]=='1':
    CT+=1

moda=[1]
modb=[1]
modc=[1]
for i in range(n-1):
  if CT>=2:
    moda.append(moda[-1]*2%(CT-1))
  if CT>=1:
    modb.append(modb[-1]*2%CT)
  modc.append(modc[-1]*2%(CT+1))


x.reverse()
za=0
zb=0
zc=0
for i in range(n):
  if x[i]=='1':
    if CT>=2:
      za+=moda[i]
      za%=(CT-1)
    if CT>=1:
      zb+=modb[i]
      zb%=CT
    zc+=modc[i]
    zc%=(CT+1)
x.reverse()
moda.reverse()
modc.reverse()

for i in range(n):
  y2=x[i]
  if y2=='1':
    ct1=CT-1
  else:
    ct1=CT+1
  if ct1==0:
    print(0)
  else:
    if y2=='1':
      z=za
      z-=moda[i]
      z%=ct1
    else:
      z=zc
      z+=modc[i]
      z%=ct1
    
    ans=1
    while z!=0:
      z=ct[z]
      ans+=1
    print(ans)

Measured memory_bytes: 139116
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pb push_back
#define eb emplace_back
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2 vector<vec>
#define vecll2 vector<vecll>
#define vec3 vector<vec2d>
#define vecll3 vector<vecll2d>
#define fi first
#define se second
#define endl "\n"
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> inline void print(vector<T> v){for(T e:v)cout<<e<<" ";cout<<endl;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
void print(vector<vec> v){for(auto e:v){for(auto ee:e)cout<<ee<<" ";cout<<endl;}}
void print(map<int,int> mp){for(auto e:mp)cout<<e.first<<" "<<e.second<<endl;cout<<endl;}

int m[1100][1100];
int tmp[2200][2200];
int r1[2200][2200];
int r2[2200][2200];
main(){
    int n=in();
    vec a;rep(i,n)a.pb(in());
    int sum=0;
    rep(i,n)sum+=a[i];
    int d=INT_MAX;
    int ans;
    rep(i,n){
        if(abs(sum-a[i]*n)<d){
            d=abs(sum-a[i]*n);
            ans=i;
        }
    }
    cout<<ans<<endl;
}


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

#define ll long long
#define db double
#define deb(x) cout<<#x<<": "<<x<<"\n"
#define all(x) x.begin(),x.end()
#define fo(i, n) for(i=0 ; i<n ; i++)
#define Fo(i, k, n) for(i=k ; i<n ; i++)

using namespace std;

const ll mod = 1000000007;
const ll N = 300005;  // array size
const ll inf = 10000000000000000;


void print(vector<ll> v) {
    ll i;
    fo(i, v.size())cout << v[i] << " ";
    cout << "\n";
}

vector<ll> read(ll n) {
    ll i;
    vector<ll> arr(n, 0);
    fo(i, n)cin >> arr[i];
    return arr;
}

vector<ll> read(ll n, ll k) {
    ll i;
    vector<ll> arr(n + k, 0);
    Fo(i, k, n + k)cin >> arr[i];
    return arr;
}

bool isEven(ll n) {
    return n % 2 == 0;
}

bool isOdd(ll n) {
    return n % 2 != 0;
}


void solve() {
    ll t;
    cin >> (t);
    while (t--) {

        ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll i, j, k, n, m, p, q, x, y, a, b, l, r;


    cin >> a >> b;

    if (2 * b >=a) {
        cout << 0;
    } else {
        cout << a - 2 * b;
    }

    return 0;
}




Measured memory_bytes: 3604
# !/usr/bin/python3

"""
https://atcoder.jp/contests/abc152/tasks/abc152_d
Low Elements.
"""

def solve(n):
    res = 0

    for num in range(n+1):
        start = int(str(num)[0])
        end = int(str(num)[-1])

        for i in range(1, 10):
            for j in range(1, 10):
                if i == start and j == end: dp[i][j] += 1

    for i in range(1, 10):
        for j in range(1, 10):
            res += dp[i][j]*dp[j][i]
    # for each in dp: print(each)

    return res


if __name__ == "__main__":
    n = int(input())
    dp = [[0 for _ in range(10)] for _ in range(10)]

    print(solve(n))


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

#define pb(n) push_back(n)
#define fi first
#define se second
#define all(r) begin(r),end(r)
#define vmax(ary) *max_element(all(ary))
#define vmin(ary) *min_element(all(ary))
#define debug(x) cout<<#x<<": "<<x<<endl
#define fcout(n) cout<<fixed<<setprecision((n))
#define scout(n) cout<<setw(n)
#define vary(type,name,size,init) vector< type> name(size,init)
#define vvl(v,w,h,init) vector<vector<ll>> v(w,vector<ll>(h,init))
#define mp(a,b) make_pair(a,b)

#define rep(i,n) for(int i = 0; i < (int)(n);++i)
#define REP(i,a,b) for(int i = (a);i < (int)(b);++i)
#define repi(it,array) for(auto it = array.begin(),end = array.end(); it != end;++it)
#define repa(n,array) for(auto &n :(array))

using ll = long long;
using pii = pair<int,int> ;
using pll = pair<ll,ll> ;

template<typename T>
void O(T t){
  cout << t << endl;
}

const ll mod = 1e9+7;
constexpr ll inf = ((1<<30)-1)*2+1 ;
constexpr double PI = acos(-1.0) ;
double eps = 1e-10 ;
const int dy[] = {-1,0,1,0,1,-1,1,-1};
const int dx[] = {0,-1,0,1,1,-1,-1,1};

inline bool value(int x,int y,int w,int h){
  return (x >= 0 && x < w && y >= 0 && y < h);
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n,k,ans = 1;
  cin >> n >> k;
  ans = k;
  rep(i,n-1){
    ans = ((k-1) * ans) ;
  }
  cout << ans << endl;
  return 0;
}


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



int main() {
    int h, n; cin >> h >> n;
    vector<int> dam(n), mp(n);
    rep(i, n) cin >> dam[i] >> mp[i];

    vector<int> dp(h+1, INF);
    dp[0] = 0;
    rep(i, h+1){
        rep(j, n){
            int index = min((int)dp.size()-1, i+dam[j]);
            chmin(dp[index], dp[i] + mp[j]);
        }
    }
    cout << dp[h] << ln;
}



Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author tatsumack
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(12)

using namespace std;

typedef pair<int, int> P;

class DFriction {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int H, W;
        cin >> H >> W;
        vector<vector<char>> G(H, vector<char>(W, 0));
        REP(i, H) {
            REP(j, W) {
                cin >> G[i][j];
            }
        }

        int res = 0;
        REP(i, W - 1) {
            vector<vector<int>> cost(H + 1, vector<int>(H + 1));
            vector<vector<int>> h(H + 1, vector<int>(H + 1));
            REP(j, H + 1) REP(k, H + 1) cost[j][k] = INF, h[j][k] = INF;
            cost[0][0] = 0;
            REP(j, H + 1) h[j][0] = 0, h[0][j] = 0;
            h[0][0] = 0;
            REP(j, H) REP(k, H) h[j + 1][k + 1] = min(h[j + 1][k + 1], h[j][k] + (G[j][i] == G[k][i + 1]));

            REP(j, H + 1) {
                REP(k, H + 1) {
                    if (j + 1 <= H) cost[j + 1][k] = min(cost[j + 1][k], cost[j][k] + h[H - j][H - k]);
                    if (k + 1 <= H) cost[j][k + 1] = min(cost[j][k + 1], cost[j][k] + h[H - j][H - k]);
                }
            }
            res += cost[H][H];
        }
        cout << res << endl;
    }
};


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);

    DFriction solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 1864
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

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

        static void Main(string[] args)
        {
            string S = Read();
            int N = S.Length;
            int cnt = 0;
            for (int i = 0; i < N / 2; ++i)
            {
                if (S[i] != S[N - i - 1]) { ++cnt; }
            }
            Console.WriteLine(cnt);
        }
    }
}


Measured memory_bytes: 13140
N = int(input())

import collections

count = collections.defaultdict(int)


for x in range(1, 10000):
    for y in range(1, 10000):
        if x*x + y*y + 1 + x*y + y + x > 10000:
            break
        for z in range(1, 100000):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n > 10000:
                break
            else:
                count[n] += 1
# print(count)

for i in range(1, N+1):
    if i not in count:
        print(0)
    else:
        print(count[i])

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

int N;
const int MAX_N = 1.0e5 + 100;
int a[MAX_N];

int main() {
    cin >> N;
    for (int i = 0; i < N; i++) cin >> a[i];

    ll e_sum = 0;
    ll even = 0;
    for (int i = 0; i < N; i++) {
        e_sum += a[i];
        if (i % 2 == 0 && e_sum <= 0) {
            even += abs(e_sum) + 1;
            e_sum = 1;
        }
        else if (i % 2 == 1 && e_sum >= 0) {
            even += abs(e_sum) + 1;
            e_sum = -1;
        }
    }

    ll o_sum = 0;
    ll odd = 0;
    for (int i = 0; i < N; i++) {
        o_sum += a[i];
        if (i % 2 == 1 && o_sum <= 0) {
            odd += abs(o_sum) + 1;
            o_sum = 1;
        }
        else if (i % 2 == 0 && o_sum >= 0) {
            odd += abs(o_sum) + 1;
            o_sum = -1;
        }
    }

    cout << min(even, odd) << endl;
    
    return 0;
}


Measured memory_bytes: 640
//Author ::  ABHINAV3010 ::

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fast ios_base::sync_with_stdio(false)
typedef long long ll;
typedef pair<ll,ll> p;
ll mod=1000000007;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
ll power(ll x, ll y, ll p=mod)
{ll res = 1;x = x % p;while (y > 0){if (y & 1){res = (res*x) % p;}y = y>>1;x = (x*x) % p;}return res;}
int main()
{
fast;
ll n,k,c;
cin>>n>>k>>c;
string s;
cin>>s;
//vector<ll>pos1,po2;
if(c==0)
{
    ll y=0;
    for(ll i=0;i<n;i++)
    {
        if(s[i]=='o')
        {
           y++;
        }
    }
    if(y!=k)
    {
        return 0;
    }
}
ll prev=INT_MAX;
ll cnt=0;
unordered_map<ll,ll>mp;
for(ll i=n-1;i>=0;i--)
{
    if(s[i]=='o')
    {
        if(prev-i>c&&cnt<k)
        {
            cnt++;
            prev=i;
            mp[i]++;
        }
    }
}
if(cnt!=k)
{
    return 0;
}
prev=INT_MIN;
cnt=0;
vector<ll>ans;
for(ll i=0;i<n;i++)
{
    if(s[i]=='o')
    {
      if(i-prev>c&&cnt<k)
      {
          cnt++;
          prev=i;
          if(mp.count(i)>0)
          {
              ans.pb(i+1);
          }
      }
    }
}
if(cnt!=k)
{
    return 0;
}
sort(all(ans));
for(ll i=0;i<ans.size();i++)
{
    cout<<ans[i]<<endl;
}
return 0;
}


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

#define CO const
#define IN inline
typedef long long int64;

template<class T> IN T read(){
	T x=0,w=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*w;
}
template<class T> IN T read(T&x){
	return x=read<T>();
}

CO int mod=1e9+7,i2=(mod+1)/2;
IN int add(int a,int b){
	return (a+=b)>=mod?a-mod:a;
}
IN int mul(int a,int b){
	return (int64)a*b%mod;
}
IN int fpow(int a,int b){
	int ans=1;
	for(;b;b>>=1,a=mul(a,a))
		if(b&1) ans=mul(ans,a);
	return ans;
}

CO int N=310;
int fac[N],ifac[N];
int d[N],f[N][N][2];

int main(){
	int n=read<int>();
	fac[0]=1;
	for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
	ifac[n]=fpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(int i=1;i<=n;++i) read(d[i]);
	f[0][0][0]=1;
	for(int i=0;i<n;++i)for(int j=0;j<=i;++j){
		f[i+1][j][0]=add(f[i+1][j][0],mul(f[i][j][0],ifac[d[i+1]-1]));
		f[i+1][j][1]=add(f[i+1][j][1],mul(f[i][j][1],ifac[d[i+1]-1]));
		if(d[i+1]<2) continue;
		f[i+1][j+1][0]=add(f[i+1][j+1][0],mul(f[i][j][0],ifac[d[i+1]-2]));
		f[i+1][j+1][1]=add(f[i+1][j+1][1],mul(f[i][j][1],ifac[d[i+1]-2]));
		if(d[i+1]<3) continue;
		f[i+1][j+1][1]=add(f[i+1][j+1][1],mul(f[i][j][0],ifac[d[i+1]-3]));
	}
	int ans=0;
	for(int j=3;j<n;++j)
		ans=add(ans,mul(f[n][j][1],mul(fac[n-j-1],mul(fac[j-1],i2))));
	if(n>=3) ans=add(ans,mul(f[n][n][0],mul(fac[n-1],i2)));
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1024