akhauriyash/Code-Regression huggingface dataset:
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cherrypi59
 */

#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FFOR(i, a, b) FOR(i, a, b+1)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) FOR(i, 1, n+1)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define LEN(x) (int)(x).size()
#define DUMP(x) cerr<<__LINE__<<' '<<#x<<"="<<(x)<<endl;
#define pb push_back
#define eb emplace_back
#define mp make_pair

using namespace std;
using lint = long long;
using pii =  pair<int, int>;
using pll =  pair<lint, lint>;
template <typename T> using vc = vector<T>;
template <typename T> using vvc = vector<vector<T>>;
template <typename T> inline bool chmax(T &a, T b){if(a<b){a = b; return true;} return false;}
template <typename T> inline bool chmin(T &a, T b){if(a>b){a = b; return true;} return false;}

constexpr lint ten(int n) {return n==0 ? 1 : ten(n-1)*10;}

class BNiceShopping {
public:
    void solve(std::istream& in, std::ostream& out){
        ios_base::sync_with_stdio(false);
        in.tie(nullptr), out.tie(nullptr);
        int A, B, M;
        in>>A>>B>>M;
        vc<int> a(A), b(B), x(M), y(M), c(M);
        REP(i, A) in>>a[i];
        REP(i, B) in>>b[i];
        REP(i, M){
            in>>x[i]>>y[i]>>c[i];
            x[i]--, y[i]--;
        }
        int ans = *min_element(ALL(a)) + *min_element(ALL(b));
        REP(i, M){
            chmin(ans, a[x[i]]+b[y[i]]-c[i]);
        }
        out<<ans<<'\n';
    }
};


int main() {
	BNiceShopping solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 2176
// #include <bits/stdc++.h>
// #define ll long long int
// #define vi vector<ll>
// #define vvi vector<vector<ll>>
// #define pii pair<ll, ll>
// #define pb push_back
// #define rep0(i, n) for(ll i = 0;i<n;i++)
// #define rep1(i, n) for(ll i = 1;i<n;i++)
// #define all(v) v.begin(),v.end()
// #define fast                          
//     ios_base::sync_with_stdio(false); 
//     cin.tie(NULL);                    
//     cout.tie(NULL);
// using namespace std;
// const int N = 2e5 + 5;

// vector<int> vis(N, 0);
// vector<int> adj[N];
// int mx = 0;

// int dfs(int u){
//     int ans = 0;
//     if(!vis[u]){
//         vis[u] = true;
//         ans++;
//         for(auto v: adj[u]){
//             ans += dfs(v);
//         }
//     }
//     return ans;
// }

// void solve(){
//     int n, m;
//     cin >> n >> m;
//     for(int i=0; i<m; i++){
//         int x, y;
//         cin >> x >> y;
//         x--;y--;
//         adj[x].push_back(y);
//         adj[y].push_back(x);
//     }
//     for(int i=0; i<n; i++){
//         if(!vis[i]){
//             mx = max(mx, dfs(i));
//         }
//     }
//     cout << mx;
// }
 
// int main()
// {
//     fast;
//     solve();
//     // int t;
//     // cin >> t;
//     // while(t--){
//     //     solve();
//     // }
//     return 0;
// }
#include <bits/stdc++.h>
#define ll long long int
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<ll, ll>
#define pb push_back
#define rep0(i, n) for(ll i = 0;i<n;i++)
#define rep1(i, n) for(ll i = 1;i<n;i++)
#define all(v) v.begin(),v.end()
#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
using namespace std;
const int N = 1e5 + 5;

vector<int> parent;

int find(int x){
    if(parent[x] == x){
        return x;
    }
    else{
        int a = find(parent[x]);
        parent[x] = a;
        return a;
    }
}

void connect(int x, int y){
    parent[find(x)] = find(y);
}

void solve(){
    int n, m;
    cin >> n >> m;
    parent.resize(n);
    for(int i=0; i<n; i++){parent[i] = i;}
    for(int i=0; i<m; i++){
        int x, y;
        cin >> x >> y;
        x--;y--;
        connect(x, y);
    }
    vector<int> temp(n, 0);
    for(int i=0; i<n; i++){
        temp[find(parent[i])]++;
    }
    cout << *max_element(temp.begin(), temp.end());
}
 
int main()
{
    fast;
    solve();
    // int t;
    // cin >> t;
    // while(t--){
    //     solve();
    // }
    return 0;
}


Measured memory_bytes: 7804
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

fn f(A: i64, B: i64, x: i64) -> i64 {
    (A * x / B) - A * (x / B)
}

fn main() {
    let mut scan = Scan::new();

    let A = scan.word::<i64>();
    let B = scan.word::<i64>();
    let N = scan.word::<i64>();

    let M = if B - 1 <= N {
        f(A, B, B - 1)
    } else {
        f(A, B, N)
    };

    println!("{}", M)
}


Measured memory_bytes: 2160
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    ll n, m;
    cin >> n >> m;
    if(n%2)
    {
        for(int i=1, j=n-1; i<=m; i++, j--)
        {
            cout << i << " " << j << endl;
        }
    }
    else
    {
        bool is_half = false;
        for(int i=1, j=n-1; i<=m; i++, j--)
        {
            if(!is_half && j-i <= n/2)
            {
                is_half = true;
                j--;
            }
            cout << i << " " << j << endl;
        }
    }
    
    
    return 0;
}


Measured memory_bytes: 3492
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define DEFAULT LL ans=solve();\
 	if(ans==NONE){\
 	}else{\
 		cout << ans << endl;\
 	}
#define YESNO three(solve(),(OUT(YES),1),(OUT(NO),0))
#define YesNo three(solve(),OUT(Yes),OUT(No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b-1);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,zero,b)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<pr, Vpr > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 5e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE1;
const int MAPSIZE = 40;
const LL p998 = 998244353;
const LL p107 = 1000000007;
const LL p = p107;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
const LL NONE=-2;
#define endl "\n"
ut N, M,K,  Q, D, H, W;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
//LL A[SIZE],B[SIZE],C[SIZE];
LL solve(){
	string s;
	cin >> s;
	LL ans=0;
	LL alpha=0;
	REP(i,s.size()){
		if(s[i]=='?') s[i]='D';
	}
	cout << s << endl;
	return NONE;
}
 signed main() {
 
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	LL T=1;

	REP(i,T){
		DEFAULT;

	}
	
//	YesNo;
//	YESNO;
//	three(solve(),OUT("First"),OUT("Second"));
	//cin >> N;
	return 0;
 
}


Measured memory_bytes: 15536
#include <ctype.h>
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <signal.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

//char rbuf[]; int rbufl;
//#define getchar() rbuf[rbufl++]
#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); bool s=false; if(c=='-'){s=true;c=getchar();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar(); int s=0; if(c=='-'){s=1;c=getchar();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar(); while(c==' '||c=='\n') c=getchar(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar(); } *s='\0'; return len; }
void printint(int32_t x){ if(x<0){x=-x; putchar('-');}else if(x==0){putchar('0');} int d=0; char s[10]; while(x){ s[d]='0'+x%10; x/=10; d++; } for (int i=d-1; i>=0; i--) putchar(s[i]); putchar('\n'); }
void rsorta_d32(void *base, const int count, const int size, const int index){
	typedef int32_t rsort_t;
	rsort_t (*a)[size] = (rsort_t(*)[size])base;
	rsort_t (*b)[size] = (rsort_t(*)[size])malloc(count*size*sizeof(rsort_t));
	int c[0x100];
	for(int k=0; k<4; k++){
		memset(c, 0, sizeof(c)); for(int i=0; i<count; i++){ c[(a[i][index]>>(k<<3))&0xFF]++; } for(int i=1; i<0x100; i++) c[i]+=c[i-1]; for(int i=count-1; i>=0; i--){ int to=--c[(a[i][index]>>(k<<3))&0xFF]; for(int j=0; j<size; j++){ b[to][j]=a[i][j]; } }{rsort_t(*t)[size]=a; a=b; b=t;}
	}
	free(b);
}

int p[200000][2];
int main(void){
	int n=nextint();
	for(int i=0; i<n; i++){
		p[i][0]=nextint();
		p[i][1]=nextint();
	}
	int a1 = p[0][0]-p[0][1];
	int a2 = p[0][0]-p[0][1];
	int b1 = p[0][0]+p[0][1];
	int b2 = p[0][0]+p[0][1];
	for(int i=1; i<n; i++){
		{ long now=p[i][0]-p[i][1]; if(now>a1) a1=now; if(now<a2) a2=now; }
		{ long now=p[i][0]+p[i][1]; if(now>b1) b1=now; if(now<b2) b2=now; }
	}
	long ans1=a1-a2;
	long ans2=b1-b2;
	printf("%ld\n", ans1>=ans2?ans1:ans2);
}


Measured memory_bytes: 3168
import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  ppp = []
  ppm = []
  pmp = []
  pmm = []
  mpp = []
  mpm = []
  mmp = []
  mmm = []
  for _ in range(N):
    x, y, z = map(int, input().split())
    ppp.append(x+y+z)
    ppm.append(x+y-z)
    pmp.append(x-y+z)
    pmm.append(x-y-z)
    mpp.append(-x+y+z)
    mpm.append(-x+y-z)
    mmp.append(-x-y+z)
    mmm.append(-x-y-z)
  ppp = sorted(ppp, key=lambda x:-x)
  ppm = sorted(ppm, key=lambda x:-x)
  pmp = sorted(pmp, key=lambda x:-x)
  pmm = sorted(pmm, key=lambda x:-x)
  mpp = sorted(mpp, key=lambda x:-x)
  mpm = sorted(mpm, key=lambda x:-x)
  mmp = sorted(mmp, key=lambda x:-x)
  mmm = sorted(mmm, key=lambda x:-x)

  ans = max(sum(ppp[:M]), sum(ppm[:M]), sum(pmp[:M]), sum(pmm[:M]),
            sum(mpp[:M]), sum(mpm[:M]), sum(mmp[:M]), sum(mmm[:M]))
  print(ans)


if __name__ == '__main__':
  main()

Measured memory_bytes: 3444
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
#include <set>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << 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;}

int main() {
  int a, b;
  cin >> a >> b;
  if (b % a == 0) P(a + b);
  else P(b - a);
  return 0;


}

Measured memory_bytes: 256
#include <stdio.h>

int sumDigits(int x){
    int i, n = 0;
    for(i = 0; x > 0; i++){
        n += x%10;
        x /= 10;
    }
    return n;
}
int main() {
    int N, A, B;
    scanf("%d", &N);

    N = sumDigits(N);
    if(N == 1)
        N = 10;

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

    return 0;
}

Measured memory_bytes: 128
import numpy as np
from numba import njit

MOD = 1000000007


@njit('(i8[:], i8)', cache=True)
def solve(dp, S):
    dp[3: 6] = 1
    d = 0
    for i in range(6, S + 1):
        d += dp[i - 3] % MOD
        dp[i] = (d + 1) % MOD
    return dp[S]


S = int(input())
dp = np.empty(S + 1, dtype=np.int64)
dp[:3] = 0
ans = solve(dp, S)
print(ans)

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

int main()
{
	char ch;
	int cnt[26] = {0};

	while(cin >> ch)
	{
		ch = tolower(ch);
		if(isalpha(ch))
		{
			cnt[ch - 'a']++;
		}
	}
	for(int i = 0; i < 26; i++)
	{
		printf("%c : %d\n", i + 'a', cnt[i]);
	}

	return 0;
}

Measured memory_bytes: 3112
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<cmath>
#include<sstream>
#include<iomanip>
#include <map>
#include <stack>

struct max_min
{
    int64_t max = 0;
    int64_t min = 0;
};

const int64_t cc = pow( 10, 9 ) + 7;
//std::cout<< std::fixed << std::setprecision(10) << ( double )( max ) / 2;
bool sort_pair( std::pair< int64_t, int64_t > origin, std::pair< int64_t, int64_t > another )
{
    return origin.first < another.first;
}

int main()
{
    std::string word = "aa";
    std::string w = "Yes";
    int64_t a,b,c,d,e,f;
    std::cin>> a;
    std::cin>> b;

    if( a * 500 < b )
    {
        w = "No";
    }

    std::cout<< w;
}


Measured memory_bytes: 256
import math
N,L = input().split()
N,L = int(N),int(L)
#c = math.gcd(N,L)

if(L>=0):
    print(int(0.5*N*(N+1)+N*L-N-(L)))
else:
    n = min([-L,N-1])
    print(int(0.5*N*(N+1)+N*L-N-(L+n)))

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

int main() {
	int n,a,b,c,sum;
  	cin>>n;

	vector<bool> vec(n+1,0);
  vec.at(1)=1;
  	for(int i=2;i<40;i++){
    	a=i*i;
      while(a<=n){
      	vec.at(a)=1;
        a *=i;
      }
    }
  
  for(int i=n;i>0;i--){
  	if(vec.at(i)==1){
    	cout<<i<<endl;
      break;
    }
  }
  
  	
  
  
return 0;
}

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

fn main() {
    let (n, y) = get!(i32, i32);

    if n * 10_000 < y {
        println!("-1 -1 -1");
        return;
    }

    for i in 0..n + 1 {
        for j in 0..n + 1 - i {
            let t = n - i - j;
            if t < 0 {
                continue;
            }
            if 10_000 * i + 5000 * j + 1000 * t == y {
                println!("{} {} {}", i, j, t);
                return;
            }
        }
    }
    println!("-1 -1 -1");
}


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

int main() {
  int a, b, c, x;
  cin >> a;
  cin >> b;
  cin >> c;
  cin >> x;

  int cnt = 0;
  for(int na=0; na <= a; na++)
  {
    for(int nb=0; nb <= b; nb++)
    {
      for(int nc=0; nc <= c; nc++)
      {
        int y = 500*na + 100*nb + 50*nc;
        if(x == y)
        {
          cnt++;
        } 
      }
    }
  }

  cout << cnt << endl;
    
  return 0;
}


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

int main() {
  int a;
  cin>>a;
  int p,count=0;
  
  for(int i=0;i<a;i++){
    cin>>p;
    if(p%2==1){
      count++;
    }
  }
  
  if(count%2==1){
    cout<<"NO"<<endl;
  }
  else{
    cout<<"YES"<<endl;
  }      
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	C
# CreatedDate:  2020-09-04 13:08:51 +0900
# LastModified: 2020-09-04 13:26:51 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        if A[i] >= B[i]:
            ans += B[i]
            A[i] -= B[i]
        elif A[i] < B[i] and A[i+1] < B[i]-A[i]:
            ans += A[i+1] + A[i]
            A[i+1] = 0
            A[i] = 0
        elif A[i] < B[i] and A[i+1] >= B[i]-A[i]:
            ans += B[i]
            A[i+1] -= B[i]-A[i]
            A[i] = 0
#        print(A)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 24156
def main():
	_, t, *L = map(int, open(0).read().split())
	d = [0] * (t + max(L[::2]))
	for w, v in sorted((x, y) for x, y in zip(*[iter(L)] * 2)):
		for i in range(t + w - 1, w - 1, -1):
			if d[i - w] + v > d[i]:
				d[i] = d[i - w] + v
	print(max(d))

if __name__=="__main__":
	main()

#vs after contest

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

using namespace std;

#define int 	long long
#define endl	"\n"
#define mod		1000000007
#define IOS		ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

int32_t main(){

	IOS
	int n;
	string s;
	cin >> n ;
	unordered_set<string> items;

	while(n--) {

		cin >> s;
		items.insert(s);

	}

	cout << items.size();

	return 0;
}

Measured memory_bytes: 17636
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define Rep(i, n) for(int i=0;i<n;++i)
#define rep(i, n) for(int i=1;i<=n;++i)
#define ll long long int
#define INF 1e9
#define LINF 1e18
#define MOD 1000000007
#define PI 3.14159265359
#define eps 1e-10
#define All(a) (a).begin(), (a).end()

using namespace std;
using P = pair<ll, ll>;
 
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

/**
 * Usage:
 * 
 * G[from].push_back(Edge(to, weight));
 * using Graph = vector<vector<Edge>>;
 * 
 */ 
struct Edge {
  int to;     
  ll weight; 
  Edge(int t, ll w) : to(t), weight(w) { }
};

/**
 * Usage:
 * 
 * chmin(old, new);
 * chmax(old, new);
 * 
 */ 
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template<typename T>
void printv(vector<T>& v) {
  if (v.size() == 0) {
    cout << "\n";
    return;
  }

  Rep(i, v.size()) {
    cout << v[i] << ((i + 1 < v.size()) ? ' ' : '\n');
  }
}



int N;
int a[60];
int b[60];
int dp[1 << 18][51];

int main () {
  cin >> N;

  Rep(i, N) cin >> a[i];
  Rep(i, N) cin >> b[i];

  Rep(bits, 1<<N) {
    Rep(i, 51) dp[bits][i] = INF;
  }
  dp[0][0] = 0;

  Rep(bits, 1<<N) {
    Rep(lst, 51) {
      bitset<20> bt(bits);

      if (dp[bits][lst] == INF) continue;

      int done = 0;
      Rep(i, N) {
        if (bt[i]) done++;
      }

      Rep(i, N) {
        if (bt[i]) continue;

        int p = abs(done - i) % 2;
        if (p == 0) {
          if (a[i] < lst) continue;
        } else {
          if (b[i] < lst) continue;
        }

        int c = 0;
        Rep(j, i) {
          if (!bt[j]) c++;
        }

        if (p == 0) {
          chmin(dp[bits | (1<<i)][a[i]], dp[bits][lst] + c);
        } else {
          chmin(dp[bits | (1<<i)][b[i]], dp[bits][lst] + c);
        }
      }
    }
  }

  int ans = INF;
  Rep(i, 51) chmin(ans, dp[(1 << N) - 1][i]);

  if (ans == INF) ans = -1;
  cout << ans << "\n";

}

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);


using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

const char sp = ' ';
const char cmm = ',';
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powmod(ll b, ll e){ll r=1;while(e>0){if(e&1)r=(r%MOD)*(b%MOD)%MOD;b=(b%MOD)*(b%MOD)%MOD;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T>
void ppp(T n){cout << n << endl;}
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
	int len = v.size();
    s << '[';
	for (int i = 0; i < len; ++i) {
		s << v[i]; if (i < len-1) s << ", ";
	}
    s << ']';
	return s;
}

struct aaa{
    aaa(){
        cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);
    };
}fastio;

ll a, b, c, d;

ll cnt(ll x){
	ll o = x - (x/c + x/d - x/lcm(c, d));
	return o;
}

int main(){

	cin >> a >> b >> c >> d;

	cout << cnt(b)-cnt(a-1) << endl;


    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ss second
#define ff first
using namespace std;
const int M = 1000000007;

int mod(int x, int m = M){
    x %= m;
    return x < 0 ? x+m : x;
}


signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin>>n;

    cout<<n + pow(n,2) + pow(n,3)<<endl;


}

Measured memory_bytes: 4304
#include<bits/stdc++.h>
#define fi first
#define se second
#define show(x) cerr<<#x<<"="<<x<<"\n"
typedef long long ll;
template<typename T>
void print_to(std::ostream &os,const char *,const char *tail,const T &fst){
  os<<fst<<tail;
}
template<typename Fst,typename... Rst>
void print_to(std::ostream &os,const char *del,const char *tail,const Fst &fst,const Rst &... rst){
  os<<fst<<del;
  print_to(os,del,tail,rst...);
}
template<typename Iter>
void print_to_(std::ostream &os,const char *del,const char *tail,Iter bgn,Iter end){
  for(Iter it=bgn;it!=end;){
    os<<*it;
    if(++it!=end)os<<del;
    else os<<tail;
  }
}
template<typename Fst,typename... Rst>
void println(const Fst &fst,const Rst &... rst){
  print_to(std::cout,"\n","\n",fst,rst...);
}
template<typename Fst,typename... Rst>
void print(const Fst &fst,const Rst &... rst){
  print_to(std::cout," ","\n",fst,rst...);
}
template<typename Iter>
void println_(Iter bgn,Iter end){
  print_to_(std::cout," ","\n",bgn,end);
}
template<typename Iter>
void println__(Iter bgn,Iter end){
  print_to_(std::cout,"\n","\n",bgn,end);
}
using namespace std;
//const ll MOD=(ll)1e9+7;
//const ll inf=(ll)1e14;
const int dy[]={1,0,-1};
const int dx[]={1,0,-1};
ll n,m,h,w;
string s;
map<pair<int,int>,ll> mp;
int x[100001],y[100001];
ll ans[10];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
  FILE *stream1;
  //FILE *stream2;
  stream1=freopen("in","r",stdin);
  //stream2=freopen("out","w",stdout);
  if(stream1==NULL)return 0;
  //if(stream2==NULL)return 0;
#endif
  cin>>h>>w>>n;
  for(int i=0;i<n;i++){
    cin>>y[i]>>x[i];
    x[i]--;y[i]--;
    for(int j=-2;j<=0;j++){
      for(int k=-2;k<=0;k++){
        if(y[i]+j<0 || y[i]+j+2>=h)continue;
        if(x[i]+k<0 || x[i]+k+2>=w)continue;
        mp[make_pair(y[i]+j,x[i]+k)]++;
      }
    }
  }
  for(auto ite=mp.begin();ite!=mp.end();ite++){
    //auto temp=ite->fi;
    //int temp2=ite->se;
    //print((temp.fi),(temp.se),temp2);
    ans[ite->se]++;
  }
  ans[0]=(w-2)*(h-2)-(int)mp.size();
  println__(ans,ans+10);
#ifdef LOCAL_DEFINE
  cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
  fclose(stream1);
  //fclose(stream2);
#endif
  return 0;
}






Measured memory_bytes: 57344
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define INF 1e9


int main(void){
    int N;
    cin>>N;
    vector<ll> h(N+2);
    for (int i=0;i<N;i++) cin>>h[i];
    vector<ll> dp(N+2,INF);

    dp[0]=0;

    for (int i=0;i<N;i++){
        if (dp[i+1] > dp[i] + abs(h[i]-h[i+1])){
            dp[i+1] = dp[i] + abs(h[i]-h[i+1]);
        }
        if (dp[i+2] > dp[i] + abs(h[i]-h[i+2])){
            dp[i+2] = dp[i] + abs(h[i]-h[i+2]);
        }
        
    }

    cout<<dp[N-1]<<endl;


    return 0;
}

Measured memory_bytes: 1792
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define ll long long
#define ull unsigned long long
#define INF (1 << 30)
#define LLINF (1LL << 62)
#define MOD7 1000000007
#define MOD9 1000000009
#define eps 1e-9
#define P pair<int, int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pul pair<ull, ull>
#define all(a) (a).begin(), (a).end()
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);--i)
#define REP(i,n) for (int i=0;i<(n);++i)
#define RREP(i,n) for (int i=(n)-1;i>=0;--i)

void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void yes() { cout << "yes" << endl; }
void no() { cout << "no" << endl; }

template<class T>
class DirectedGraph {
public:
	class Edge {
	public:
		int to;
		T cost;

		Edge(int t, T c) : to(t), cost(c) {}

		bool operator<(const Edge& right) const {
			return cost == right.cost ? to < right.to : cost < right.cost;
		}
	};

	vector<vector<Edge>> G;
	int V;

	DirectedGraph(int n = 0) {
		resize(n);
	}

	void resize(int n) {
		V = n;
		G.resize(n);
	}

	void addEdge(int from, int to, T cost = 0) {
		int v = max(from, to);
		if (v >= V)
			resize(v + 1);
		G[from].push_back(Edge(to, cost));
	}


	int t = 1;
	vector<pii> stamp;
	vector<bool> visit;
	void dfs(int s) {
		visit.resize(V);
		stamp.resize(V);
		calcDfs(s);
	}

	void calcDfs(int s) {
		if (visit[s])
			return;

		stamp[s].first = t++;

		visit[s] = true;
		for (int i = 0; i < G[s].size(); ++i) {
			calcDfs(G[s][i].to);
		}

		stamp[s].second = t++;
	}

	vector<int> bfs() {

	}
};

int main() {
	DirectedGraph<int> g;
	int n, id, k, to;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> id >> k;
		while (k--) {
			cin >> to;
			g.addEdge(id, to);
		}
	}

	for (int i = 1; i <= n; ++i)
		g.dfs(i);

	for (int i = 1; i <= n; ++i) {
		printf("%d %d %d\n", i, g.stamp[i].first, g.stamp[i].second);
	}

	return 0;
}

Measured memory_bytes: 3200
#include <iostream>
#include <set>
#include <string>

int main()
{
    std::set<std::string> dict;

    int commandNum = 0;
    std::cin >> commandNum;

    std::string command;
    std::string setter;
    for (int i = 0; i < commandNum; i++)
    {
        std::cin >> command >> setter;

        if (command == "insert")
        {
            dict.insert(setter);
        }
        else if (command == "find")
        {
            if (dict.count(setter)) std::cout << "yes" << std::endl;
            else                    std::cout << "no"  << std::endl;
        }
    }
}


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

int main(){
    long N, K;
    cin >> N >> K;
    long A[N+1];
    long S[N+1];
    S[0]=0;
    for(long i=1; i<N+1; i++){
        cin >> A[i];
        S[i]=S[i-1]+A[i];
    }

    long ans=0;
    unordered_map<long, long> mp;
    for(long j=1; j<=N; j++ ){
        if( j-K >= 0 ){
            mp[ (S[j-K]-(j-K))%K ] -= 1;
            //cout << "delete j K i " << j << " " << K << " " << j-K << endl; 
        }
        if( j-1 >= 0 ){
            mp[ (S[j-1]-(j-1))%K ] += 1;
            //cout << "add j 1 i " << j << " " << 1 << " " << j-1 << endl; 
        }
        ans += mp[ (S[j]-j)%K ];
        //cout << "j ans " << j << " " << ans << endl;
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 11592
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//abc141D
int compare_int(const void *a, const void *b) {
  return *(int*) a - *(int*) b;
}

int main(void) {
  int n, m, i, j, cou=0;
  long long sum=0;
  scanf("%d %d", &n, &m);
  int a[n];

  for(i=0; i < n; i++) scanf("%d", &a[i]);

  qsort(a, n, sizeof(int), compare_int);
  i=n - 1;
  while(cou < m){
    if(i == -1) i=n - 1;//配列の先頭を超えたら末尾から再開
    else if((i == n - 1) || (a[i] > a[n-1])) a[i--]/=2, cou++;//末尾OR末尾の要素より大
    else{
      qsort(a, n, sizeof(int), compare_int);
      i=n - 1;
    }
  }
  for(i=0;i<n;i++)sum+=a[i];
  printf("%lld",sum);
}

Measured memory_bytes: 892
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[] numEle = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		int num = sc.nextInt();
		System.out.println(numEle[ num - 1]);
		}
	}



Measured memory_bytes: 22868
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<stdio.h>
using namespace std;
 
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define INF 1<<25
 
int main()
{
	int A, B;
	cin >> A >> B;
	cout << (A - 1) * (B - 1) << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    char str[128];

    scanf("%s", str);

    int num;
    for (num=0; str[num] != '\0'; num++);

    int i, count = 0;
        for (i = 0; i < num / 2; i++) {
            if (str[i] != str[(num-1) - i])
                count++;
        }

    printf("%d", count);
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<numeric>
#include<math.h>
#include<algorithm>
#include<iomanip>
using namespace std;

int main() {

	int N;
	int X;
	cin >> N;
	cin >> X;

	vector<int> L(N, 0);
	for (int i = 0; i < L.size(); i++) {
		cin >> L[i];
	}

	int D = 0;
	int ans = 0;
	if (D <= X) {
		ans += 1;
	}
	for (int i = 0; i < L.size(); i++) {
		D = D + L[i];
		if (D <= X) {
			ans += 1;
		}
	}

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

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000
#define NIL -1

struct Node { int p, l, r; };

typedef struct Node node;

node T[MAX];

void preParse(int u) {

  if ( u == NIL) return;
  printf(" %d", u);
  preParse(T[u].l);
  preParse(T[u].r);

}

void inParse(int u) {

  if ( u == NIL ) return;
  inParse(T[u].l);
  printf(" %d", u);
  inParse(T[u].r);

}

void postParse(int u) {

  if ( u == NIL ) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d", u);

}

void print(int root){

    printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

}

void scan(){

  int i,n,v,l,r;
  node T[MAX];
  
  for (i = 0; i < n; i++) {

    scanf("%d %d %d", &v, &l, &r);

    
    T[v].l = l; T[v].r = r;

    if ( l != NIL ) T[l].p = v;

    if ( r != NIL ) T[r].p = v;

    return;
    
  }

  return;
}
  

int main() {

  int n;
  
  int i, v, l, r, root;

  scanf("%d", &n);
  
  for (i = 0; i<n; i++ ) {

    T[i].p = NIL;

  }
  
  for (i = 0; i < n; i++) {

    scanf("%d %d %d", &v, &l, &r);

    
    T[v].l = l; T[v].r = r;

    if ( l != NIL ) T[l].p = v;

    if ( r != NIL ) T[r].p = v;
    else continue;

  }

  for (i = 0; i<n; i++ ){
    if ( T[i].p == NIL ) root = i;
  }
  
  print(root);

  return 0;
}



Measured memory_bytes: 2108
#include<iostream>

using namespace std;

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

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
using namespace std;
int n, a[200010];
int m[1000010];
int main()
{
    std::cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (!m[a[i]])
        {
            for (int j = a[i]; j <= 1000000; j += a[i])
            {
                m[j] = true;
            }
            if (i == n - 1 || a[i] != a[i + 1]) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8292
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define cs const 
#define fr first 
#define se second
#define ls (now<<1)
#define rs (now<<1|1)
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
#define ppb pop_back
#define low(i) (i&(-i))
#define par pair<int,int>
#define cn(x) memset(x, 0, sizeof(x))
#define rep(i, x, y) for(int i=x; i<=y; ++i)
#define sep(i, x, y) for(int i=x; i>=y; --i)
#define fore(i, x) for(int i=fir[x]; i; i=nex[i])
 
cs int G = 3;
cs int ff = 2e6 + 1;
cs int inf = 1e18 + 1;
cs int base = 2333;
cs int M = 1e9 + 7;

int n, m, b[ff], c[ff], qz[ff];
int ksm(int x, int y) {return (y ? ksm(x * x % M, y / 2) : 1) * (y % 2 == 1 ? x : 1) % M;
}
void init()
{
	cin >> n;
	if(n == 1) {cout << 0; return;}
	cout << ((ksm(10, n) - ksm(9, n) * 2 % M + ksm(8, n)) % M + M) % M;
}
signed main()
{
	int Ts = 1;
	while(Ts--)
		init();
}

Measured memory_bytes: 3636
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		int[][] map = new int[n+1][n+1];
		Treasure[] treasure = new Treasure[n];
		
		for(int i=0;i<n;i++) {
			treasure[i] = new Treasure(sc.nextInt(),sc.nextInt());
		}
		
		Arrays.sort(treasure,new ComparatorX());
		for(int i=0;i<n;i++) {
			x[i] = treasure[i].x * 2;
			treasure[i].xindex = i;
		}
		
		Arrays.sort(treasure,new ComparatorY());
		for(int i=0;i<n;i++) {
			y[i] = treasure[i].y * 2;
			treasure[i].yindex = i;
		}
		
		for(int i=0;i<n;i++) {
			map[treasure[i].xindex+1][treasure[i].yindex+1]++;
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				map[i][j] += map[i-1][j];
			}			
		}
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				map[i][j] += map[i][j-1];
			}			
		}
		for(int i=0;i<m;i++) {
			int x1 = sc.nextInt()*2;
			int y1 = sc.nextInt()*2;
			int x2 = sc.nextInt()*2;
			int y2 = sc.nextInt()*2;
			x1 = binarySearch(x, x1-1)+1;
			y1 = binarySearch(y, y1-1)+1;
			x2 = binarySearch(x, x2+1)+1;
			y2 = binarySearch(y, y2+1)+1;
			System.out.println(map[x2][y2]-map[x2][y1]-map[x1][y2]+map[x1][y1]);
		}
		
	}
	public static int binarySearch(int[] array,int num) {
		int first = 0;
		int last = array.length-1;
		int center = (first+last)/2;
		while(first<=last) {
			if (center<array.length-1) {
				if (array[center] < num) {
					if (num < array[center+1]) {
						return center;
					}else{
						first = center+1;
					}
				}else{
					last = center-1;
				}
			}else{
				return array.length-1;
			}
			center = (first+last)/2;
		}
		return -1;
	}
	
}
class Treasure {
	int x=0;
	int y=0;
	int xindex = 0;
	int yindex = 0;
	public Treasure(int x,int y) {
		this.x = x;
		this.y = y;
	}
}
class ComparatorX implements Comparator<Treasure> {
	public int compare(Treasure t1,Treasure t2) {
		return t1.x-t2.x;
	}
}
class ComparatorY implements Comparator<Treasure> {
	public int compare(Treasure t1,Treasure t2) {
		return t1.y-t2.y;
	}
}

Measured memory_bytes: 559980
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
using ll = long long;

constexpr int P = 1000000007;

ll inv(int n) {
    int m = P, y = 0, v = 1;
    while (1) {
        int q = m / n;
        int r = m % n;
        if (r == 0) return v < 0 ? v + P : v;
        y -= v * q;
        swap(y, v);
        m = n;
        n = r;
    }
}

int comb(int n, int k) {
    if (n < k || k < 0) return 0;
    ll t = 1;
    k = min(k, n - k);
    for (int i = 2; i <= k; i++) {
        t = (t * i) % P;
    }
    t = inv(t);
    for (int i = n - k + 1; i <= n; i++) {
        t = (t * i) % P;
    }
    return t;
}

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

    int t = x + y;
    if (t % 3 != 0) {
        cout << 0 << endl;
        exit(0);
    }

    t /= 3;//移動回数
    x -= t;
    y -= t;
    if (x < 0 || y < 0) {
        cout << 0 << endl;
        exit(0);
    }

    cout << comb(t, x) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << #x << ": " << x << '\n'

typedef long long int Int;
typedef pair<int,int> P;
using ll = long long;
using VI = vector<int>;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main(){
    int H,N;cin >> H >> N;
    vector<int> a(N),b(N);
    for(int i=0;i<N;i++) cin >> a[i] >> b[i];
    vector<ll> dp(H+1,INF);
    dp[0] = 0;
    for(int i=0;i<N;i++){
        for(int j=0;j<=H;j++){
            chmin(dp[min(j+a[i],H)],dp[j]+b[i]);
        }
    }
    cout << dp[H] << endl;
}

Measured memory_bytes: 384
#include<stdio.h>
	int main(){
		int a[5],s[14],p[14],i,j,c,g,h,d;
		while(scanf("%d,%d,%d,%d,%d",&a[0],&a[1],&a[2],&a[3],&a[4])!=EOF){
			g=0;
			h=0;
			d=0;
			c=0;
			for(i=0;i<14;i++){
				s[i]=i+1;
				p[i]=0;
			}
			s[13]=1;
			for(i=0;i<13;i++)
				for(j=0;j<5;j++)
				if(a[j]==s[i]){
				p[i]++;
				if(a[j]==1)
					p[13]++;
			}
			for(i=0;i<10;i++)
				if(p[i]==1){
					
					for(j=i+1;j<i+5;j++){
						
						if(p[j]!=1)
							break;
						if(j==i+4){
							printf("straight\n");
							c++;
						}
					}
					
			}
			if(c>0)
				continue;
			for(i=0;i<13;i++){
				if(p[i]==4)d++;
				if(p[i]==3)g++;
				if(p[i]==2)h++;
			}
			if(d>0)
				printf("four card\n");
			else if(g>0&&h>0)
				printf("full house\n");
			else if(g>0&&h==0)
				printf("three card\n");
			else if(g==0&&h==1)
				printf("one pair\n");
			else if(g==0&&h==2)
				printf("two pair\n");
			else printf("null\n");
		}
		return 0;
}

Measured memory_bytes: 0
#include <algorithm>
#include <cctype>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 2e3+5;
struct Edge
{
    int next, to;
    Edge(int next = 0, int to = 0):next(next), to(to) {};
}edge[N<<1];
int head[N], tot;
void _add(int x, int y) { edge[++tot] = Edge(head[x], y); head[x] = tot; }
void add(int x, int y) { _add(x, y); _add(y, x); }
int n, k;
void dfs(int x, int fa, int *d)
{
    for(int i = head[x]; i; i = edge[i].next)   
    {
        int y = edge[i].to; if(y == fa) continue;
        d[y] = d[x]+1; dfs(y, x, d);
    }
}
int d[N][N], ans;
int main()
{
    n = read(), k = read(), ans = n;
    for(int i = 1; i < n; ++i) 
    {
        int x = read(), y = read();
        add(x, y);
    }
    for(int x = 1; x <= n; ++x) dfs(x, 0, d[x]);
    if(k&1)
    {
        for(int i = 1; i <= tot; i += 2)
        {
            int u = edge[i].to, v = edge[i+1].to, c = 0;
            for(int y = 1; y <= n; ++y) c += d[u][y] > k/2&&d[v][y] > k/2;
            ans = min(ans, c);
        }
    }
    else
    {
        for(int x = 1; x <= n; ++x) 
        {
            int c = 0;
            for(int y = 1; y <= n; ++y) c += d[x][y] > k/2;
            ans = min(ans, c);
        }
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 16000
using System;
using System.Linq;//リストの使用
using System.Collections.Generic;
class Program
{
	static void Main()
	{
  int[] nums = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
  int n = nums[0];
  int m = nums[1];
  int x = nums[2];
  int y = nums[3];
	int[] lefts = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
  int[] rights = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);
  Array.Sort(lefts);
  Array.Sort(rights);
	//出力
    if(lefts[n-1] < y && x < rights[0] && lefts[n-1] < rights[0])
    {
    Console.WriteLine("No War");
    }
    else Console.WriteLine("War");
	}
}


Measured memory_bytes: 13140
// https://atcoder.jp/contests/abc174/tasks/abc174_c
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

void solve() {
    int K;
    cin >> K;
    int t = 0;
    REP(i, K + 1) {
        t = t * 10 + 7;
        if (t % K == 0) {
            cout << i + 1 << endl;
            return;
        }
        t %= K;
    }
    cout << -1 << endl;
}
signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


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

int main() {
   string s,t;
   cin>>s>>t;
  
  int a,b;
  cin>>a>>b;
  
  string u;
  cin>>u;
  
  if(u==s){
  	cout<<a-1<<" "<<b<<endl;
  }
  
  else{
  	cout<<a<<" "<<b-1<<endl;
  }


}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while(true){

            String input = br.readLine();

//          ???????????¶
            if(input.equals("-")){
                break;
            }
//          ?????£??????????????°shuffle
            int shuffle = Integer.parseInt(br.readLine());

            for(int i = 0; i < shuffle; i++){
                int h = Integer.parseInt(br.readLine());
                input = input.substring(h) + input.substring(0, h);
            }
            System.out.println(input);
        }
    }
}

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

int main() {
  int N, M, max_score = 0;
  cin >> N;
  vector<string> blue(N);

  for (int i = 0; i < N; i++) {
    cin >> blue.at(i);
  }

  cin >> M;
  vector<string> red(M);
  for (int i = 0; i < M; i++) {
    cin >> red.at(i);
  }

  for (int i = 0; i < N; i++) {
    int score = 0;
    for (int j = 0; j < N; j++) {
      if (blue.at(i) == blue.at(j)) score++;
    }
    for (int j = 0; j < M; j++) {
      if (blue.at(i) == red.at(j)) score--;
    }
    if (max_score < score) max_score = score;
  }
  cout << max_score << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string>
#include<utility>
#include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<bitset>

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0;i<(int)(n);i++)

int judge(char a,char b){
    int aa=a-'0';
    int bb=b-'0';
    if(aa==0 && bb!=0)return 1;
    else if(aa==1){
        if(bb==1||bb==2)return 1;
    }
    return -1;
}

int main(){
    char s[4]={};
    scanf("%s",s);
    int a1=judge(s[0],s[1]);
    int a2=judge(s[2],s[3]);
    //printf("%d %d\n",a1,a2);
    if(a1==1 && a2==-1)printf("MMYY\n");
    else if(a1==1  && a2==1)printf("AMBIGUOUS\n");
    else if(a1==-1  && a2==1)printf("YYMM\n");
    else printf("NA\n");
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod = 1e9 + 7;

int main() {
  ll a, b, n;
  cin >> n >> a >> b;
  ll x = n / (a + b);
  ll y = n % (a + b);
  if (y > a)
    cout << x * a + a << endl;
  else
    cout << x * a + y << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int ans = a * b;
    if(ans % 2 == 0){
      System.out.println("Even");
    }else{
      System.out.println("Odd");
    }
}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main()
{
int N,M;
cin>>N>>M;
vector<long>H(N);
for(int i=0;i<N;i++)
{cin>>H[i];}

vector<int>A(M);
vector<int>B(M);
for(int i=0;i<M;i++)
{cin>>A[i]>>B[i];}

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

for(int i=0;i<M;i++)
{
if(H[A[i]-1]>=H[B[i]-1]){points[B[i]-1]++;}
if(H[B[i]-1]>=H[A[i]-1]){points[A[i]-1]++;}

}
int answer=0;
for (int i=0;i<N;i++)
{if(points[i]==0){answer++;}}

cout<<answer<<endl;


}



Measured memory_bytes: 4992
n,a,b = map(int,input().split())
m = 10**9 + 7
comb_a = 1
comb_b = 1

a_num = list(range(1,a+1))
j = 0
for i in range(1,a+1):
    comb_a *= (n-i+1)
    comb_a *= pow(a_num[i-1],m-2,m)
    comb_a = comb_a % m

b_num = list(range(1,b+1))
j = 0
for i in range(1,b+1):
    comb_b *= (n-i+1)
    comb_b *= pow(b_num[i-1],m-2,m)
    comb_b = comb_b % m

ans = pow(2,n,m) - comb_a - comb_b - 1
print(int(ans) % m)

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

int main() {
  long long x;
  cin >> x;
  long long money = 100;
  int ans = 0;
  while (true) {
    money *= 1.01;
    ans++;
    if (money >= x) {
      cout << ans << endl;
      break;
    }
  }
}

Measured memory_bytes: 3624
package main

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

var sc *bufio.Scanner

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

func main() {
	sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	m, d := nextInt(), nextInt()

	ans := 0
	for mth := 1; mth <= m; mth++ {
		for div := 2; div <= 9; div++ {
			if mth/div < 10 && mth/div > 1 && mth%div == 0 {
				if (mth/div)*10+div <= d {
					ans++
				}
				if div*10+(mth/div) <= d {
					ans++
				}
			}
		}
	}
	fmt.Println(ans / 2)
}


Measured memory_bytes: 640