akhauriyash/Code-Regression huggingface dataset:
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <limits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class T> inline string toString(T x) { ostringstream sout; sout << x; return sout.str(); }

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x * x; }

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

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

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

	sort(a.begin(), a.end());

	//元の符号が正は正、負は負でまとめておく
	vector<int> pos;
	vector<int> neg;

	for (int i = 1; i < n - 1; i++) {
		if (a[i] >= 0) {
			pos.push_back(a[i]);
		}
		else {
			neg.push_back(a[i]);
		}
	}

	//手順を記録する配列
	vector<pair<int, int>> res;

	//最終的に+にしたい分を一つ残してまとめて-側に突っ込む

	int base = a[n-1] - a[0];

	if (pos.size() > 0) {
		base = -base;
		//右端と左端を核にして、+→-の順でまとめてくっつけたい
		res.push_back(make_pair(a[0], a[n - 1]));
	}
	else {
		//右端と左端を核にして、+→-の順でまとめてくっつけたい
		res.push_back(make_pair(a[n - 1], a[0]));
	}

	if (pos.size() > 0) {
		for (int i = 0; i < pos.size() - 1; i++) {
			res.push_back(make_pair(base, pos[i]));
			base -= pos[i];
		}

		//残しておいた最後の+で-をまとめてひっくり返す
		res.push_back(make_pair(pos[pos.size() - 1], base));
		base = pos[pos.size() - 1] - base;
	}
	

	//-にしたい分を全部くっつける
	for (int i = 0; i < neg.size(); i++) {
		res.push_back(make_pair(base, neg[i]));
		base -= neg[i];
	}

	//出力
	cout << base << endl;
	for (int i = 0; i < res.size(); i++) {
		cout << res[i].first << " " << res[i].second << endl;
	}

	return 0;
}


Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=j; i<=k; i++)
#define FFOR(i, j, k) for(int i=j; i<k; i++)
#define DFOR(i, j, k) for(int i=j; i>=k; i--)
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "C"
int n;
int a;
int cnt[100001];
int main(){
    #ifdef Megumin
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Megumin
    read(n);
    FOR(i, 1, n){
        read(a);
        cnt[a]++;
    }
    if(n%2) cnt[0]++;
    for(int i=n-1; i>=0; i-=2) if(cnt[i]!=2){
        puts("0");
        return 0;
    }
    int ans=1;
    DFOR(i, n/2, 1) ans=(ans*2)%1000000007;
    writeln(ans);
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*"lcm"   MIN*/                      int lcm(ll a,ll b){return a*b/gcd(a,b);}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int main() {
string a,b,c;
cin >> a >> b >> c;
char z = a.at(0);
 a = a.substr(1,100);
 while(1){
    if(z=='a'){
       if(a.size()==0){cout<<"A"<<endl; return 0;}
       z = a.at(0);
       a = a.substr(1,100);
    }
    if(z=='b'){
       if(b.size()==0){cout<<"B"<<endl; return 0;}
       z = b.at(0);
      b = b.substr(1,100);
    }
    if(z=='c'){
       if(c.size()==0){cout<<"C"<<endl; return 0;}
       z = c.at(0);
       c = c.substr(1,100);
    }


 }
}




Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

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

    cout << (N - 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  ll N, X, Y; cin >> N >> X >> Y;
  for (ll k = 1; k <= N-1; k++) {
    ll num = 0;
    for (ll x = 1; x <= N-k; x++) {
      ll y = x+k;
      if (y-x < abs(x-X)+abs(y-Y)+1) {num++;}
    }
    for (ll x = 1; x <= N; x++) {
      if (k-1-abs(x-X) >= 0) {
        ll y = Y+k-1-abs(x-X);
        if (y <= N && k <= y-x) {num++;}
        y = Y-(k-1-abs(x-X));
        if (y >= 1 && k <= y-x && k-1-abs(x-X) > 0) {num++;}
      }
    }
    cout << num << endl;
  }
}

Measured memory_bytes: 256
import sys

def propare():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))
    B = int(next(tokens))

    solve(A, B)

def solve(A: int, B: int):
    if A < 10 and B < 10 :
        print(A * B)
    else:
        print(-1)


    return


 
if __name__ == "__main__":
    propare()

Measured memory_bytes: 3060
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define MOD = 1000000007
#define INF (1e9)
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;


int main()
{
    string s;
    cin >> s;
    ll cnt = 0;
    rep(i, 4) {
        if (s[i] == '+') cnt++;
        else cnt--;
    }
    print(cnt);
    return 0;
}


Measured memory_bytes: 256
n=int(input())
ans=0
import itertools
for i in range(1,n+1):
    p,q=str(i)[0],str(i)[-1]
    if int(p)*int(q)==0:
        continue
    if len(str(i))>=3:
        if p<q:
            ans+=int("1"*(len(str(i))-2))*2
        elif p>q:
            ans+=int("1"*(len(str(i))-1))*2
        else:
            ans+=int("1"*(len(str(i))-2))*2
            ans+=(int(str(i)[1:-1])+1)*2
            ans+=1
    elif len(str(i))==1:
        ans+=1
    else:
        if p>q:
            ans+=2
        elif p==q:
            ans+=3
print(ans)


Measured memory_bytes: 3064
Program ABC159C
   implicit none
   integer::L,i,j
   real(8)::Vmax=0,xmax,ymax,zmax,x,y,z,V

      read *,L
      do i=1,100
         x=real(L)/100.0*real(i)
         do j=1,100
            y=(real(L)-x)/100.0*real(j)
            z=real(L)-x-y
            V=x*y*z
            if (V>Vmax) then
               Vmax=V
               xmax=x
               ymax=y
               zmax=z
            end if
         end do
      end do

      do i=-50,50
         x=xmax+real(L)/10000.0*real(i)
         do j=-50,50
            y=ymax+real(L)/10000.0*real(j)
            z=real(L)-x-y
            V=x*y*z
            if (V>Vmax) then
               Vmax=V
            end if
         end do
      end do

      print *,Vmax
      stop

   End Program ABC159C

Measured memory_bytes: 384
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
#include <memory.h>
#include <iomanip>
#include <bitset>
#include <list>
#include <stack>
#include <deque>
#include <numeric>

using namespace std;

#define mod 1000000007

int n, c;
int a[410];
int b[410];

// powsum[i][j] = 0^i + 1^i + ... + (j - 1)^i
long long int powsum[410][410] = {};

long long int getpow(int x, int a)
{
	if(a == 0) return 1;
	if(a == 1) return x;
	long long int tmpres = getpow(x, a / 2);
	long long int ans = (tmpres * tmpres) % mod;
	if(a % 2 == 1) ans = (ans * x) % mod;
	return ans;
}

void getpowsum()
{
	for(int i = 0; i <= 400; i++){
		for(int j = 1; j <= 401; j++){
			powsum[i][j] = (powsum[i][j - 1] + getpow(j - 1, i)) % mod;
		}
	}
}

long long int result[401][401] = {};

long long int solve(int now, int rest)
{
	if(result[now][rest] > 0) return result[now][rest];
	long long int ans = 0;
	if(now == n - 1){
		ans = (powsum[rest][b[now] + 1] - powsum[rest][a[now]] + mod) % mod;
	} else {
		for(int i = 0; i <= rest; i++){
			long long int tmpres = (powsum[i][b[now] + 1] - powsum[i][a[now]] + mod) % mod;
			tmpres = (tmpres * solve(now + 1, rest - i)) % mod;
			ans = (ans + tmpres) % mod;
		}
	}
	return result[now][rest] = ans;
}

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

Measured memory_bytes: 2816
n = int(input())
a = [list(map(int,input().split())) for i in range(n-1)]
for i in range(n):
  time = 0
  for j in range(i,n-1):
    t,s,f = a[j]
    if time < s:
      time = s
    elif time % f == 0:
      time = time
    else:
      time = (time + f) - (time % f)
    time += t
  print(time)

Measured memory_bytes: 3188
# coding: utf-8


def solve(*args: str) -> str:
    h, w, k = map(int, args[0].split())

    cakes = [[0 for _ in range(w)] for _ in range(h)]
    n = 1

    for y, A in enumerate(args[1:]):
        cnt = A.count('#')
        if cnt == 0:
            if 0 < y:
                for x in range(w):
                    cakes[y][x] = cakes[y-1][x]
        else:
            for x, a in enumerate(A):
                cakes[y][x] = n
                if a == '#' and 1 < cnt:
                    n += 1
                    cnt -= 1
            n += 1

    for y in reversed(range(h)):
        for x in range(w):
            if cakes[y][x] == 0:
                cakes[y][x] = cakes[y+1][x]

    return '\n'.join(' '.join(map(str, cakes[i])) for i in range(h))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


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

int main() {
    string s;
    int cnt = 0;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'R') {cnt++;}
    }

    if (s[1] == 'S') {cnt = min(1, cnt);}
    cout << cnt << endl;

}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long

const int N = 2000001;

int n, k, fact[N], inv[N], mod = 1e9 + 7;
string s;

int powlog(int a, int b){
    if(b == 0) return 1;
    int ret = powlog(a, b / 2);
    if(b % 2) return 1LL * ret * ret % mod * a % mod;
    return 1LL * ret * ret % mod;
}
int C(int n, int r){
    if(r > n) return 0;
    return 1LL * fact[n] * inv[n - r] % mod * inv[r] % mod;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    fact[0] = 1;
    for(int i = 1 ; i < N ; i++){
        fact[i] = 1LL * i * fact[i - 1] % mod;
    }
    inv[N - 1] = powlog(fact[N - 1], mod - 2);
    for(int i = N - 2 ; i >= 0 ; i--){
        inv[i] = 1LL * (i + 1) * inv[i + 1] % mod;
    }
    cin >> k >> s;
    n = s.size();
    int ans = 0;
    for(int i = 0 ; i <= k ; i++){
        ans = (ans + 1LL * powlog(25, k - i) * powlog(26, i) % mod * C(n - 1 + k - i, n - 1)) % mod;
    }
    cout << ans << endl;
}


Measured memory_bytes: 19880
#include<iostream>
#include<string>
#include<math.h>
#include<algorithm>
using namespace std;

int main(){

	int N;
	int A, B;

	cin >> N;

	if (N == 1) cout << "Hello World" << endl;
	else {
		cin >> A >> B;
		cout << (A + B) << endl;
	}


}

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

vector<int> check(string& s){
    vector<int> v;
    int c = 0;
    map<char, int> m;
    for(int i=0; i<s.size(); i++){
        if(m.count(s[i]) == 0){
            c++;
            m[s[i]] = c;
            v.push_back(c);
        }else{
            v.push_back(m[s[i]]);
        }
    }
    return v;
}

int main()
{
    string s,t;
    cin >> s >> t;
    auto sv = check(s);
    auto tv = check(t);
    for(int i=0; i<sv.size(); i++){
        if(sv[i] != tv[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


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

int main() {
	int x_1;
	int x_2;
	int x_3;
	int x_4;
	int x_5;
	cin >> x_1;
	cin >> x_2;
	cin >> x_3;
	cin >> x_4;
	cin >> x_5;
	int i; (1<=i<=5);
	
	if (x_1<1){
	cout<<1<<endl;
	}
	else if (x_2<1){
	cout<<2<<endl;
	}
	else if (x_3<1){
	cout<<3<<endl;
	}
	else if (x_4<1){
	cout<<4<<endl;
	}
	else if (x_5<1){
	cout<<5<<endl;
	}
	
	
	return 0;
}

Measured memory_bytes: 3568
#include <cstdio>

using namespace std;

int main()
{
    int a,i;
    scanf("%d", &a);
    for(i = 1; i <= 9; ++ i)
        if(a % i == 0 && a / i <= 9)
        {
            printf("Yes");
            return 0;
        }
    printf("No");
    return 0;
}


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

int main() {
	int N, a[100], sum = 0;
	
	cin >> N;

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

	sort(a, a + N, greater<int>());

	for (int i = 0; i < N; i++) {
		if (i % 2 == 0) sum += a[i];
		else sum -= a[i];
	}

	cout << sum;

	return 0;
}


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

public class Main {
    static PrintWriter out;
    static CF_Reader in;

    public static void main(String[] args) throws IOException {
        out = new PrintWriter(new OutputStreamWriter(System.out));
        in = new CF_Reader();

        int n = in.intNext(), k = in.intNext();
        int[] arr = in.nextIntArray(n);

        int[] dp = new int[n];
        dp[0] = 0;
        dp[1] = Math.abs(arr[1] - arr[0]);

        for (int i = 2; i < n; i++) {
            int minIdx = Math.max(i - k, 0);
            int minVal = Integer.MAX_VALUE;
            for (int j = minIdx; j < i; j++) {
                minVal = Math.min(minVal, (dp[j] + Math.abs(arr[j] - arr[i])));
            }
            dp[i] = minVal;
        }
        out.println(dp[n-1]);

        out.close();
    }


    static class CF_Reader {
        BufferedReader br;
        StringTokenizer st;

        public CF_Reader() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine().trim());
            return st.nextToken();
        }

        long longNext() throws IOException {
            return Long.parseLong(next());
        }

        int intNext() throws IOException {
            return Integer.parseInt(next());
        }

        double doubleNext() throws IOException {
            return Double.parseDouble(next());
        }

        char charNext() throws IOException {
            return next().charAt(0);
        }

        public int[] nextIntArray(final int n) throws IOException {
            final int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = intNext();
            return a;
        }

        public long[] nextLongArray(final int n) throws IOException {
            final long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = longNext();
            return a;
        }

        String line() throws IOException {
            return br.readLine().trim();
        }
    }
}




Measured memory_bytes: 36788
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end())
#define VRSORT(v) sort(v.rbegin(), v.rend())//vectorの降順ソート
#define ll long long
#define pb(a) push_back(a)
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef pair<int, P> PP;
typedef pair<ll, LP> LPP;

typedef vector<unsigned int>vec;
typedef vector<vec> mat;
typedef tuple<ll, ll, ll> T;

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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    ll odd=0;
    REP(i,n){
        ll num;
        cin>>num;
        if(num%2==1) odd++;
    }
    if(odd%2==1) cout<<"NO";
    else cout<<"YES";
    cout<<endl;

}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<string.h>

#define M 1000009
#define L 14


char H[M][L]; /* Hash Table */

int getChar(char ch){
  if ( ch == 'A') return 1;
  else if ( ch == 'C') return 2;
  else if ( ch == 'G') return 3;
  else if ( ch == 'T') return 4;
}

/* convert a string into an integer value */
long long getKey(char str[]){
  long long sum = 0, p = 1, i;
  for ( i = 0; i < strlen(str); i++ ){
    sum += p*(getChar(str[i]));
    p *= 5;
  }
  return sum;
}

int h1(int key){ return key % M; }
int h2(int key){ return 1+ key %(M-1); }

int find(char str[]){

  int i=0;
  int j;

  
  int sum;
  sum=getKey(str);
  
  
  
  while(1){
    j=(h1(sum)+i*h2(sum))%M;
    //printf("now find %d %s\n",j,str);


    
    if(strcmp(H[j],str)==0) {return 1;break;}
    
    else if(strlen(H[j])==0){return 0;break;}

    else {i++;}
  }
  

  
}





int insert(char str[]){
  int i=0;
  
  int sum;
  int h;

  sum=getKey(str);
  while(1){
    
    h=(h1(sum)+i*h2(sum))%M;

    if(strlen(H[h])==0){
    strcpy(H[h],str);
    break;}
  i++;
  }
  
}






int main(){
  int i, h,n;

    char str[L], com[9];
    
    scanf("%d", &n);
    
    for ( i = 0; i < n; i++ ){
	scanf("%s %s", com, str);


	
	if ( com[0] == 'i' ){insert(str);}


	else {

	  if (find(str)==1){printf("yes\n");}
	  
	  else {printf("no\n");}
	}
    }

    return 0;
}



Measured memory_bytes: 15416
#include <stdio.h>
#include <math.h>


int main(void) {
	int n, x;
	int m;
	int sum = 0, min = 9999;

	scanf("%d %d", &n, &x);
	for (int i = 0; i < n; ++i) {
		scanf("%d", &m);
		sum += m;
		min = fmin(min, m);
	}

	int ans;
	if (sum < x) {
		ans = n + ((x - sum) / min);
	}
	else {
		ans = n;
	}

	printf("%d", ans);

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
 
using namespace std;
const int maxn=1e5+500;
 
struct node{
	int p;
	int y;
	int id;
}a[maxn];
 
pair<int,int>pa[maxn];
 
bool cmp(node a,node b){
	if(a.p!=b.p)
		return a.p<b.p;
	else
		return a.y<b.y;
}
 
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>a[i].p>>a[i].y;
		a[i].id=i;
	}
	sort(a+1,a+m+1,cmp);
	int no=0;
    for(int i=1;i<=m;i++){
        if(i>1&&a[i].p!=a[i-1].p)
            no=1;
        else
            no++;
        pa[a[i].id]=make_pair(a[i].p,no);
    }
    for(int i=1;i<=m;i++)
        printf("%06d%06d\n",pa[i].first,pa[i].second);
 
} 

Measured memory_bytes: 3456
#include <numeric>
#include<iostream>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include <cstdio>
#include<algorithm>
#include <sstream>
#include<string>
#include <cmath>
#include <iomanip>
#include <string>
#include<list>
using namespace std;
#define inf 1000000007
#define int long long
#define rep(i,j,n) for(int i=j;i<n;i++)
typedef pair<int,int>  P;
struct edge{int to,cost;};
double pi = 3.141592653589793;
//使うやつはここから下に置こうな
signed main(){
    string s;cin>>s;
    stack<int> st;
    stack<P> s2;
    int sum=0;
    rep(i,0,s.size()){
        if(s[i]=='_')continue;
        else if(s[i]=='/'){
            if(!st.empty()){
                int j=st.top();
                st.pop();
                int a=i-j;
                sum+=a;
                while(s2.size()>0&&s2.top().first>j){
                    a+=s2.top().second;s2.pop();
                }
                s2.push(make_pair(j,a));
            }
        }
        else st.push(i);
    }
    vector<int> ans;
    while(s2.size()){
        ans.push_back(s2.top().second);s2.pop();
    }
    reverse(ans.begin(),ans.end());
    cout<<sum<<endl;
    cout<<ans.size();
    rep(i,0,ans.size())cout<<" "<<ans[i];cout<<endl;
    return 0;
}


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

const int INF = 1001001001;
const int NV=100100;

typedef pair<int,int> P;

P f(int x){
  int a=x%10;
  int b=0;
  while(x){
    b=x;
    x/=10;
  }
  return P(a,b);
}

int main() {
  int n;
  cin>>n;
  map<P,int> freq;
  for (int i=1; i<=n; i++){
    P p=f(i);
    freq[p]++;
  }
  int ans=0;
  for (int i=1; i<=n; i++){
    P p=f(i);
    P q(p.second, p.first);
    ans+=freq[q];
  }
  cout<<ans<<endl;  
  return 0;
}


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

int H, W;

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

queue<pair<int, int>> q;
vector<vector<int>> seen;

void bfs(vector<string> &A) {
    while (!q.empty()) {
        auto now = q.front();
        q.pop();
        REP(i, 0, 4) {
            int nh = now.first + dx[i];
            int nw = now.second + dy[i];
            if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
            if (A[nh][nw] == '#' || seen[nh][nw] != -1) continue;
            q.push(make_pair(nh, nw));
            seen[nh][nw] = seen[now.first][now.second] + 1;
        }
    }
}

int main() {
    cin >> H >> W;
    vector<string> A(H);
    REP(i, 0, H)
    cin >> A[i];

    seen.assign(H, vector<int>(W, -1));
    REP(i, 0, H) {
        REP(j, 0, W) {
            if (A[i][j] == '#') {
                q.push(make_pair(i, j));
                seen[i][j] = 0;
            } 
        }
    }
    bfs(A);

    int ans = 0;
    REP(i, 0, H) {
        REP(j, 0, W) {
            ans = max(ans, seen[i][j]);
        }
    }

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

Measured memory_bytes: 13456
fun main(args: Array<String>) = yorukatsu20a()

fun yorukatsu20a() {
    val list = (1..5).map { readLine()!!.toInt() }

    val minBy = list.filterNot { it % 10 == 0 }.minBy { it % 10 } ?: 0
    val answer = (list - minBy).map { ((it + 9) / 10) * 10 }.sum() + minBy

    println(answer)
}


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

int main() {
  int s; cin >> s;
  set<int> cnt;
  while (cnt.count(s) == 0) {
    cnt.insert(s);
    if (s % 2 == 0) s = s / 2;
    else s = 3 * s + 1;
  }
  cout << cnt.size() + 1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 200020
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int n,A,B,CC,ans,fac[N],finv[N];
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
void init(int n){
	fac[0]=1;
	for(int i=1;i<=n;++i){
		fac[i]=1LL*fac[i-1]*i%mod;
	}
	finv[n]=qpow(fac[n],mod-2);
	for(int i=n-1;i>=0;--i){
		finv[i]=1LL*finv[i+1]*(i+1)%mod;
	}
}
inline int C(int n,int m){
	return 1LL*fac[n]*finv[m]%mod*finv[n-m]%mod;
}
int main(){
	n=read(),A=read(),B=read(),CC=100LL*qpow(100-read(),mod-2)%mod;
	int tmp=qpow(A+B,mod-2);
	A=1LL*tmp*A%mod,B=1LL*tmp*B%mod;
	init(n<<1);
	for(int i=0,Ai=1,Bi=1,An=qpow(A,n),Bn=qpow(B,n);i<n;++i,Ai=1LL*Ai*A%mod,Bi=1LL*Bi*B%mod){
		ans=(ans+(1LL*An*Bi+1LL*Bn*Ai)%mod*C(n+i-1,i)%mod*(n+i))%mod;
	}
	ans=1LL*ans*CC%mod;
	printf("%d\n",ans);
	return 0;
}



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

#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define RREP(i, a, b) for (int i = (int)(a)-1; i >= (int)(b); --i)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)
#define ALL(r) (r).begin(), (r).end()

void Main() {
    // todo
    int n; cin >> n;
    vector<int> a(n); rep(i, n) cin >> a[i];
    sort(ALL(a)); reverse(ALL(a));
    int alice = 0, bob = 0;
    rep(i, n) {
        if (i % 2 == 0) {
            alice += a[i];
        } else {
            bob += a[i];
        }
    }
    cout << alice - bob << endl;
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


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

int main() 
{
    int N,X,T;
    cin>>N>>X>>T;

    int ans=0;
    while (N>0)
    {
        ans += T;
        N-=X;
    }
    
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
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)
typedef long long ll;
typedef pair<int,int> pint;
const int inf=1e9+7;
const ll longinf=1LL<<60;
const ll mod=1e9+7;
int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1};

int main(){
    int n,m;
    while(cin>>n>>m,n!=0&&m!=0){
        int a[n],c[m];
        rep(i,n){
            a[i]=0;
            rep(j,16){
                a[i]*=2;
                int x;cin>>x;
                a[i]+=x;
            }
        }
        rep(i,m){
            c[i]=0;
            rep(j,16){
                c[i]*=2;
                int x;cin>>x;
                c[i]+=x;
            }
        }
        int dp[n+1][65536];
        rep(i,n+1)rep(j,65536)dp[i][j]=0;
        for(int i=n-1;i>=0;i--)rep(j,65536){
            int pos=j|a[i];
            rep(k,m){
                int res=pos&c[k];
                dp[i][j]=max(dp[i][j],__builtin_popcount(res)+dp[i+1][pos^res]);
            }
        }
        cout<<dp[0][0]<<endl;
    }
    return 0;
}


Measured memory_bytes: 11036
#include <iostream>
#include <vector>

using namespace std;

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

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

    for (int i = k; i < n; i++) {
        cout << (a[i - k] < a[i] ? "Yes" : "No") << endl;
    }
}


Measured memory_bytes: 3988
//author : raghav_0901

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

int n;
int m;
signed main()
{
    cin>>n;
    vector<int> v(n);
    for(int &x:v) cin>>x;
    map<int,int> mp1;
    map<int,int> mp2;
    for(int i=0;i<n;i++)
    {
        mp1[i+1+v[i]]++;
        int temp = i+1-v[i];
        if(temp>0)
            mp2[temp]++;
    }
    int ans=0;
    for(auto it:mp2)
    {
        auto temp=mp1.find(it.first);
        if(temp!=mp1.end())
        {
            ans+=(it.second*temp->second);
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 21088
#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int n; cin >> n;
	int r[2000000],maxP=-2000000000,minP;
	for(int i=0;i<n;i++){
		cin >> r[i];
	}
	
	minP = r[0];
	for(int j=1;j<n;j++){
		maxP = max(r[j]-minP,maxP);
		minP = min(minP,r[j]);
	}
	cout << maxP << endl;
	return 0;
}


Measured memory_bytes: 3908
#include<stdio.h>
int main(void)
{
	int data[9],s,z,i,n;
	scanf("%d",&n);
	while(n!=0){
		for(i=0;i<9;i++){
			scanf("%d",&data[i]);
			n-=data[i];
		}
		printf("%d\n",n);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F(i,s,e) for(ll i=s;i<e;++i)

struct Sity{
    int next;
    bool check=false;
    int id;
};

int main()
{
    int n;
    ll k;
    cin>>n>>k;
    Sity sity[n];
    F(i,0,n){cin>>sity[i].next; --sity[i].next;}
    
    int tl[n]={0};
    sity[0].check=true;
    sity[0].id=0;
    F(i,1,n+1){
        tl[i]=sity[tl[i-1]].next;
        if(!sity[tl[i]].check){
            sity[tl[i]].check=true;
            sity[tl[i]].id=i;
        }
        else{
            int id=sity[tl[i]].id;
            if(k>=id) cout << tl[(k-id)%(i-id)+id]+1 << endl;
            else cout << tl[k]+1 << endl;
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 6720
# C - Attack Survival
inputNum = list(map(int, input().split()))
N = inputNum[0]
K = inputNum[1]
Q = inputNum[2]
A = [0] * N
for i in range(Q):
    a = int(input())
    A[a - 1] += 1

for a in A:
    if a <= Q - K:
        print('No')
    else:
        print('Yes')


Measured memory_bytes: 4680
using System;
using System.Linq;
using static System.Console;
class MainClass
{
    public static void Main(string[] args)
    {
        int N, i;
        var input = ReadLine().Split().Select(int.Parse).ToArray();
        N = input[0];
        i = input[1];
        WriteLine(N - i + 1);
    }
}


Measured memory_bytes: 11348
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <string>
#include <string.h>
#include <bitset>
#include <map>
#include <climits>
#include <set>

using namespace std;

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

    using l = long;
    map<l, l> hist;
    for (int i = 0; i < N; ++i)
    {
        l a;
        cin >> a;
        if (hist.count(a))
        {
            hist[a] += 1;
        }
        else
        {
            hist.insert(make_pair(a, 1));
        }
    }

    // 前後の要素数を足して一番多いビンは？
    l max_count = 0;
    for (auto p : hist)
    {
        l v = p.first;
        l c = p.second;
        auto count = c;
        if (hist.count(v - 1))
        {
            count += hist[v - 1];
        }
        if (hist.count(v + 1))
        {
            count += hist[v + 1];
        }
        max_count = max(max_count, count);
    }

    cout << max_count << endl;

    // vector<int> an(N);
    // set<decltype(an)::value_type> xs;
    // for (int i = 0; i < N; ++i)
    // {
    //     cin >> an[i];
    //     xs.insert(an[i]);
    // }

    // sort(an.begin(), an.end());
    // // auto x_min = *min_element(an.begin(), an.end());
    // // auto x_max = *max_element(an.begin(), an.end());

    // decltype(an)::value_type max_count = 0;
    // //    for (int x = x_min; x <= x_max; ++x)
    // for (auto iter = xs.begin(); iter != xs.end(); ++iter)
    // {
    //     auto x = *iter;
    //     decltype(an)::value_type count = 0;
    //     for (int i = 0; i < N; ++i)
    //     {
    //         auto a = an[i];
    //         auto diff = a - x;
    //         if (-1 <= diff && diff <= 1)
    //         {
    //             ++count;
    //         }
    //         else if (1 < diff)
    //         {
    //             break;
    //         }
    //     }
    //     max_count = max(count, max_count);
    // }
    // cout << max_count << endl;
    return 0;
}

Measured memory_bytes: 4224
# listの各要素に人数を格納. 一番後ろに全員たどり着いたら終わり

list = [0] * 6
n_move = []
time = 4

N = int(input())

for i in range(5) : 
    n_move.append(int(input()))
    
n_min = min(n_move)

if(N % n_min == 0) : 
    time += N // n_min
else : 
    time += N // n_min + 1

print(time)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
using namespace std;
int main(){
  string s;cin >> s;
  int n = s.size();int i,ans;ans = 0;
  for(i=0;i<(n+1)/2;i++){
    if (s[i] != s[n-i-1]) ans += 1;
  }
  cout << ans << endl;
}
    

Measured memory_bytes: 256
from math import sqrt, cos, radians

A, B, H, M = map(int, input().split())

ang1 = 360 * (H/12) + 30 * (M/60)
ang2 = 360 * (M/60)
ang = abs(ang1-ang2)

ans = A**2 + B**2 -2*A*B*cos(radians(ang))
print(sqrt(ans))

Measured memory_bytes: 9508
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> bs(N, K - Q);
  F0R(i, Q) {
    int a;
    cin >> a;
    bs[a - 1]++;
  }
  F0R(i, N) {
    cout << (bs[i] > 0 ? "Yes" : "No") << newl;
  }
}
#endif


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

int main() {
    long double  i;
    long long X, K, D;
    
    cin >> X >> K >> D;
  
  if(X<0)
    X = -X;
  
    i = X/D;
    if (K<i)
    cout << X-K*D;
    else {
        if( (K-X/D)%2==0 )
        cout << X%D;
        else
        cout << -(X%D-D);
    }
}



Measured memory_bytes: 3632
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
using namespace std;
using ll =long long;

int main (void) {
  int N;
  int ans=0;
  cin >> N;
  int a[N];
  double n=N;
  int b;
  double ave=0;
  for (int i=0; i<N; i++) {
    cin >> b;
    a[i]=b;
    ave=ave+a[i];
  }
  ave=round(ave/n);
  for (int i=0; i<N; i++) {
    ans=ans+(a[i]-ave)*(a[i]-ave);
  }
  cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <cmath>
#include<map>
#include<set>


using namespace std;
const long long INF = (long long) (1e18)+1;

int main() {
  long long n;
  // long long w;
  cin >> n;

  map<long long, long long> num_map;
  vector<long long> nums_v;
  for (long long i=0; i < n; ++i) {
    long long temp;
    cin >> temp;
    nums_v.push_back(temp);
    num_map[temp]++;
  }

  // set<long long> nums; // balls more than 2
  long long ans = 0;
  map<long long, long long> anss; // store ans for same key...
  for(auto itr = num_map.begin(); itr != num_map.end(); ++itr) {
      long long key = itr->first;
      long long val = itr->second;
      if (anss[key] != 0) {
        continue;
      }
      if (val >= 2) {
        long long temp = val * (val-1) / 2;
        ans += temp;
        anss[key] = temp;
      } else {
        anss[key] = 0;
      }
  }

  // cout << "yay " << ans << endl; 
  for (long long i=0; i<n; ++i) {
    long long key = nums_v[i];
    long long val = num_map[key];
    if (val < 2) {
      cout << ans<< endl;
    } else {
      long long original = anss[key];
      long long new_num = (num_map[key]-1) * (num_map[key]-2) / 2;
      long long diff = original - new_num;
      cout << (ans - diff) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 19952
#include<iostream>   
#include<cstdio>  
#include<algorithm>
#include<queue>
#include<map>
#include<string>
using namespace std;
const int row = 4;
const int maxx = 16;
const int LIMIT = 100;
struct Puzzle {
    int f[maxx], space, MD;
};

const int dx[4] = { 0, -1, 0, 1 };
const int dy[4] = { 1, 0, -1 ,0 };
const char dir[4] = { 'r','u','l','d' };
int MDT[maxx][maxx];

Puzzle state;
int limit;
int path[LIMIT];

int getAllMD(Puzzle pz) {
    int sum = 0;
    for (int i = 0; i < maxx; i++) {
        if (pz.f[i] != maxx)
            sum += MDT[i][pz.f[i] - 1];
    }
    return sum;
}

bool isSolved() {
    for (int i = 0; i < maxx; i++)
        if (state.f[i] != i + 1)
            return false;
    return true;
}

bool dfs(int depth, int prev) {

    if (state.MD == 0)
        return true;

    // 如果当前的深度加上启发值超过了限制，则进行剪枝
    if (depth + state.MD > limit)
        return false;

    int sx = state.space / row;
    int sy = state.space % row;

    Puzzle tmp;
    for (int r = 0; r < 4; r++) {
        int tx = sx + dx[r];
        int ty = sy + dy[r];
        if (tx < 0 || ty < 0 || tx >= row || ty >= row)
            continue;
        if (max(prev, r) - min(prev, r) == 2)
            continue;
        tmp = state;
        // 计算曼哈顿距离的差值，同时交换拼图
        state.MD -= MDT[tx * row + ty][state.f[tx * row + ty] - 1];
        state.MD += MDT[sx * row + sy][state.f[tx * row + ty] - 1];
        swap(state.f[tx * row + ty], state.f[sx * row + sy]);
        state.space = tx * row + ty;
        if (dfs(depth + 1, r)) {
            path[depth] = r;
            return true;
        }
        state = tmp;
    }
    return false;
}

string iterative_deepening(Puzzle in) {
    // 初始状态的曼哈顿距离
    in.MD = getAllMD(in);
    for (limit = in.MD; limit <= LIMIT; limit++) {
        state = in;
        if (dfs(0, -100)) {
            string ans = "";
            for (int i = 0; i < limit; i++)
                ans += dir[path[i]];
            return ans;
        }
    }
    return "unsolvable";
}

int main()
{
    for (int i = 0; i < maxx; i++) {
        for (int j = 0; j < maxx; j++) {
            MDT[i][j] = abs(i / row - j / row) + abs(i % row - j % row);
        }
    }
    Puzzle in;
    for (int i = 0; i < maxx; i++) {
        cin >> in.f[i];
        if (in.f[i] == 0) {
            in.f[i] = maxx;
            in.space = i;
        }
    }
    string ans = iterative_deepening(in);
    printf("%d\n", ans.size());
    return 0;
}


Measured memory_bytes: 3368
using System;

public class P
{
    public int x { get; set; }
    public int y { get; set; }
}

public class hello
{
    public static void Main()
    {
        while (true)
        {
            var n = int.Parse(Console.ReadLine().Trim());
            if (n == 0) break;
            var a = new int[n, n];
            makeMS(a, n);
            print(a, n);
        }
    }
    static void print(int[,] a, int n)
    {
        var b = new string[n, n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
                Console.Write(string.Format("{0,4}", a[i, j]));
            Console.WriteLine();
        }
    }
    static P getNXNY(int[,] a, int n, int x, int y)
    {
        var nx = x + 1;
        var ny = y + 1;
        LA1:;
        if (nx >= n) nx = 0;
        if (ny >= n) ny = 0;
        if (ny < 0) ny = n - 1;
        if (a[nx, ny] == 0) return new P { x = nx, y = ny };
        else { nx++; ny--; }
        goto LA1;
    }
    static void makeMS(int[,] a, int n)
    {
        var p = 1;
        var x = n / 2 + 1; var y = n / 2;
        a[x, y] = p++;
        while (p <= n * n)
        {
            var t = getNXNY(a, n, x, y);
            var nx = t.x;
            var ny = t.y;
            a[nx, ny] = p++;
            x = nx; y = ny;
        }
    }
}




Measured memory_bytes: 15908
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int maxn = 3e5 + 5;
const int maxm = 1e6 + 5;
const double eps = 1e-8;
const double pi = acos(-1.0);
ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a * b / gcd(a,b);}
ll poww(ll x,ll y,ll p){ll ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p;y >>= 1;}return ans % p;}
bool isp(ll x){if(x <= 1) return 0; for(ll i = 2;i * i <= x;i++){if(x % i == 0) return 0;}return 1;}
ll h,n,a[1005],b[1005],ans,dp[20005];
int main(){
 	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> h >> n;
	for(int i = 0;i < n;i++) cin >> a[i] >> b[i];
	memset(dp,0x3f,sizeof(dp));
	dp[0] = 0;
	for(int i = 0;i < n;i++){
		for(int j = a[i];j < 20005;j++) dp[j] = min(dp[j],dp[j-a[i]] + b[i]);
	}
	ll ans = inf;
	for(int i = h;i < 20005;i++) ans = min(dp[i],ans);
	cout << ans << endl;
	return 0;
}
//do smt instead of nothing! never give up!
//take care of long long!
//take care of upper or lower case e.g "yes" or "YES"?
//boundary condition! e.g. n = 0?
//brute force is always the first choice!
// print the ans to look for patterns in the data!

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

typedef long long LL;

#define REP(i, n) for(LL i = 0; i < (LL)(n); i++)
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;


namespace modCalc {
    LL add() {
        return 0;
    }
    template<typename H, typename... T>
    LL add(H h, T... t) {
        return (h + add(t...))%mod;
    }

    template<typename H, typename... T>
    LL sub(H h, T... t) {
        return (h - add(t...) + mod)%mod;
    }

    LL mul() {
        return 1;
    }
    template<typename H, typename... T>
    LL mul(H h, T... t) {
        return (h*mul(t...))%mod;
    }

    LL pow(LL x, LL y) {
        LL res = 1;
        while(y != 0) {
            if(y%2) {
                res = mul(x, res);
                y--;
            }else{
                x = mul(x, x);
                y /= 2;
            }
        }
        return res;
    }

    LL div(LL x, LL y) {
        return mul(x, pow(y, mod - 2));
    }

    LL fact(LL n) {
        LL res = 1;
        for(LL i = 1;i <= n;i++) {
            res = mul(res, i);
        }
        return res;
    }
}

using namespace modCalc;

int main() {
    LL X, Y;
    cin >> X >> Y;
    if(-X + 2*Y < 0 || 2*X - Y < 0 || (-X + 2*Y)%3 != 0 || (2*X - Y)%3 != 0) {
        cout << 0 << endl;
        return 0;
    }
    LL n, m;
    n = (-X + 2*Y)/3;
    m = (2*X - Y)/3;
    LL res = modCalc::div(fact(n + m), mul(fact(n), fact(m)));
    cout << res << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
inline void prep ()
{
  cin.tie (0);
  cin.sync_with_stdio (0);
};
const double pi = acos(-1.);
//printf(%.12lf\n,mid);
// __builtin_popcount(int) count 1's in binary
// get decimal part of number
/*
double intpart;
double thiss = modf((double)(n*m)/(double)k, &intpart);
*/
// round = (int)(num+.5)
long long mod = 1000000007;

// 32 mil = ~1 sec 
long long mymod(long long num){
  if (num< 0 && !(num%mod == 0)){
    if (mod == 1){
      return 0;
    }
    return mod-abs(num)%mod;
  }else{
    return num%mod;
  }
}
 
/*string sentence = And I feel fine...;
    istringstream iss(sentence);
*/  
 
double eps = .000000001;
int freqs[1000001];
int temp1[1000001];
int temp2[1000001];
int main ()
{
  prep();
  int n, m;
  cin >> n >> m;
  int row[n];
  int col[m];
  int rowind[n*m+1];
  int colind[n*m+1];
  for (int i=0; i<n; i++){
      cin >> row[i];
      freqs[row[i]]++;
      temp1[row[i]]++;
      rowind[row[i]] = i;
  }
  for (int i=0; i<m; i++){
      cin >> col[i];
      freqs[col[i]]++;
      temp2[col[i]]++;
      colind[col[i]] = i;
  }
  for (int i=1; i<=1000000; i++){
      if (temp1[i] > 1 || temp2[i] > 1){
          cout << 0;
          return 0;
      }
  }
  long long res = 1;
  int bigsum = 0;
  int colpass = 0;
  int rowpass = 0;
  for (int i=n*m; i>=1; i--){
      if (freqs[i] == 2){
          rowpass++;
          colpass++;
      }else if (freqs[i] == 1){
          if (temp1[i]){
              rowpass++;
              res *= colpass;
              res %= mod;
          }else{
              colpass++;
              res *= rowpass;
              res %= mod;
          }
           // if row, # of cols bigger than it
      }else{
          res *= colpass*rowpass-(n*m-i);
          res %= mod;
      }
  }
  cout << res;
  return 0; 
}


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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	int res = 0;
	for (int i = K; i <= N + 1; i++) {
		int mn = i * (i - 1) / 2;
		int mx = (N + N - i + 1) * i / 2;
		res = (res + mx - mn + 1) % MOD;
	}
	cout << res << endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    ll k;
    cin, n, m, k;
    vector<ll> sumA(n + 1, 0), sumB(m, 0);
    REP(i, 0, n) {
        ll a;
        cin, a;
        sumA[i + 1] = sumA[i] + a;
    }
    REP(i, 0, m) {
        ll b;
        cin, b;
        if (i == 0) {
            sumB[i] = b;
        } else {
            sumB[i] = sumB[i - 1] + b;
        }
    }

    ll ans = 0;
    REP(i, 0, n + 1) {
        ll rest = k - sumA[i];
        if (rest < 0) continue;
        ll cnt = upper_bound(sumB.begin(), sumB.end(), rest) - sumB.begin();
        dump(i + cnt);
        chmax(ans, i + cnt);
    }

    print(ans);

    return 0;
}


Measured memory_bytes: 6332