akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
using namespace std;
int main()
{
	int n, r;
	cin >> n >> r;
	int a=log(n)/log(r);
	cout << a+1;



	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;

struct Node {
  int key;
  Node *right;
  Node *left;
  Node *parent;
};

Node *root;
Node *NIL;

Node * treeMinimum(Node *x){
  while(x->left != NIL) x = x->left;
  return x;
}

Node * find(Node *u, int k){
  while(u != NIL && k != u->key) {
    if(k < u->key) u = u->left;
    else u = u->right;
  }
  return u;
}

Node * treeSuccessor(Node *x){
  if(x->right != NIL) return treeMinimum(x->right);
  Node *y = x->parent;
  while(y != NIL && x == y->right) {
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node *z){
  Node *y;
  Node *x;

  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);

  if(y-> left != NIL){
    x = y->left;
  }
  else x = y->right;

  if(x != NIL) {
    x->parent = y->parent;
  }

  if(y->parent == NIL) {
    root = x;
  }
  else {
    if(y == y->parent->left) {
      y->parent->left = x;
    }
    else {
      y->parent->right = x;
    }
  }

  if(y != z) {
    z->key = y->key;
  }

  free(y);
}


void insert(int k){
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->left;
    }
    else{
      x = x->right;
    }
  }

  z->parent = y;
  if(y == NIL){
    root = z;
  }
  else{
    if(z->key < y->key){
      y->left = z;
    }else{
      y->right = z;
    }
  }
}

void inorder(Node *u){
  if( u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}

void preorder(Node *u){
  if(u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main() {
  int n, i, x;
  string com;

  scanf("%d", &n);

  for(i=0; i<n; i++){
    cin >> com;
    if(com[0] == 'f'){
      scanf("%d", &x);
      Node *t = find(root, x);
      if(t != NIL) printf("yes\n");
      else printf("no\n");
    }
    else if(com == "insert") {
      scanf("%d", &x);
      insert(x);
    }
    else if(com == "print"){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
    else if(com == "delete"){
      scanf("%d", &x);
      treeDelete(find(root, x));
    }
  }

  return 0;
}



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

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

#define pb push_back
#define pf push_front
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod (ll)(1e9+7)
#define int ll

__attribute__((constructor))
void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

signed main() {
    int x = 0;
    char S[6];
    cin >> S;
    rep(i,0,4){
        if(S[i] == '+'){
            x++;
        } else {
            x--;
        }
    }

    cout << x << endl;
}

Measured memory_bytes: 256
using System.Linq;
using System;

class Program
{
    static void Main()
    {
        var NP = Console.ReadLine().Split(' ');
        var N = int.Parse(NP[0]);
        var P = int.Parse(NP[1]);
        var A = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();

        int[] a = new int[2];
        for (int i = 0; i < N; i++)
        {
            a[A[i] % 2]++;
        }

        var ans0 = Math.Pow(2, a[0]);
        var ans1 = 0.0;

        var aa = Comb(2,2);
        
        for (int i = P; i <= a[1]; i += 2)
        {
            ans1 += Comb(a[1], i);
        }

        Console.WriteLine(ans0 * ans1);
    }

    static double Comb(int n, int k)
    {
        double ans = 1;
        for (int i = 0; i < k; i++)
        {
            ans *= (double)(n - i) / (i + 1);
        }
        return ans;
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<string> s(n);
    for(int i=0;i<n;i++)cin>>s[i];
    int count[5];
    for(int i=0;i<5;i++)count[i]=0;
    for(int i=0;i<n;i++){
        switch(s[i][0]){
        case 'M':count[0]++;break;
        case 'A':count[1]++;break;
        case 'R':count[2]++;break;
        case 'C':count[3]++;break;
        case 'H':count[4]++;break;
        }
    }
    ll ans = 0;
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            for(int k=j+1;k<5;k++){
                if(count[i]&&count[j]&&count[k]){
                    ans+=((ll)count[i])*count[j]*count[k];
                }
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

#define reint register int
#define coint const int
#define codb const double

using namespace std;

codb EPS = 1e-8;

struct Vector {
    double x, y;

    inline Vector operator+(const Vector &v) const {
        return (Vector){ x + v.x, y + v.y };
    }

    inline double dot(const Vector &v) const { return x * v.x + y * v.y; }
    inline double cross(const Vector &v) const { return x * v.y - y * v.x; }
    inline double length(void) const { return sqrt(x * x + y * y); }
    inline double square(void) const { return x * x + y * y; }
    inline double getAngle(void) const { return atan2(y, x); }

    inline Vector operator*(const double a) const {
        return (Vector){ x * a, y * a };
    }
};

struct Point {
    double x, y;

    inline Vector operator-(const Point &p) const {
        return (Vector){ x - p.x, y - p.y };
    }

    inline Point operator+(const Vector &v) const {
        return (Point){ x + v.x, y + v.y };
    }
};

struct Segment {
    Point s, t;

    inline int isIntersectWith(const Segment &seg) const {
        codb minX1 = min(s.x, t.x), maxX1 = max(s.x, t.x);
        codb minY1 = min(s.y, t.y), maxY1 = max(s.y, t.y);
        codb minX2 = min(seg.s.x, seg.t.x), maxX2 = max(seg.s.x, seg.t.x);
        codb minY2 = min(seg.s.y, seg.t.y), maxY2 = max(seg.s.y, seg.t.y);
        if (minX1 - EPS > maxX2 || maxX1 + EPS < minX2
            || minY1 - EPS > maxY2 || maxY1 + EPS < minY2)
            return 0;
        const Vector vec1 = t - s, vec2 = seg.t - seg.s;
        codb prof1 = (s - seg.s).cross(vec2) * vec2.cross(t - seg.s);
        codb prof2 = (seg.s - s).cross(vec1) * vec1.cross(seg.t - s);
        if (prof1 + EPS > 0 && prof2 + EPS > 0)
            return 1;
        else return 0;
    }
};

inline int isEq(const double a, const double b) {
    return abs(a - b) < EPS;
}

int main(void) {
    int q;
    scanf("%d", &q);
    while (q--) {
        Point p0, p1, p2, p3;
        scanf("%lf%lf%lf%lf%lf%lf%lf%lf",
              &p0.x, &p0.y, &p1.x, &p1.y, &p2.x, &p2.y, &p3.x, &p3.y);
        const Segment seg1 = (Segment){ p0, p1 }, seg2 = (Segment){ p2, p3 };
        printf("%d\n", seg1.isIntersectWith(seg2));
    }

    return 0;
}



Measured memory_bytes: 3236
#include <stdio.h>
 
int main(void)
{
    int r, c, i, j;
    int a[101][101] = { 0 };
 
    scanf("%d %d", &r, &c);
 
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            scanf("%d", &a[i][j]);
 
    for (i = 0; i < r; i++)
        for (j = 0; j < c; j++)
            a[i][c] += a[i][j];
 
    for (j = 0; j <= c; j++)
        for (i = 0; i < r; i++)
            a[r][j] += a[i][j];
 
    for (i = 0; i <= r; i++)
        for (j = 0; j <= c; j++)
            printf("%d%s", a[i][j], j == c?"\n" : " ");
 
    return 0;
}

Measured memory_bytes: 648
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

fn main(){
    let mut i:Vec<i32> = read_vec();
    if i[0] > i[1] {
        let tmp = i[0];
        i[0] = i[1];
        i[1] = tmp;
    }
    if i[1] > i[2] {
        let tmp = i[1];
        i[1] = i[2];
        i[2] = tmp;
    }
    if i[0] > i[1] {
        let tmp = i[0];
        i[0] = i[1];
        i[1] = tmp;
    }
    println!("{} {} {}", i[0], i[1], i[2]);
}


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

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> P;

class CFolia {
public:
    void solve(std::istream& cin, std::ostream& cout) {
        int N;
        cin >> N;
        vector<int> A(N + 1);
        REP(i, N + 1) cin >> A[i];

        if (A[0] > 1) {
            cout << -1 << endl;
            return;
        }
        if (A[0] == 1) {
            if (N == 0) {
                cout << 1 << endl;
            } else {
                cout << -1 << endl;
            }
            return;
        }

        vector<int> par(N + 1);
        par[0] = 1;
        for (int i = 1; i <= N; i++) {
            par[i] = par[i - 1] * 2 - A[i];
            if (par[i] < 0) {
                cout << -1 << endl;
                return;
            }
            if (par[i] > INF) {
                par[i] = INF;
            }
        }

        vector<int> num(N + 1);
        num[N] = A[N];
        for (int i = N - 1; i >= 0; i--) {
            num[i] = min(num[i + 1], par[i]) + A[i];
        }
        int res = 0;
        for (int i = 0; i <= N; i++) res += num[i];
        cout << res << endl;
    }
};


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

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


Measured memory_bytes: 5576
//B - Palindromic Numbers
//https://atcoder.jp/contests/abc090/tasks/abc090_b

#include <cstdio>

int pow(int, int);

int main()
{
  int A, B;
  int N = 0;
  scanf("%d", &A);
  scanf("%d", &B);

  for (int i = A; i < B + 1; i++)
  {
    int i1 = i;
    int i2 = i;
    bool tf = true;
    for (int j = 0; j < 2; j++)
    {
      int n1, n2;
      n1 = i1 % 10;
      n2 = i2 / pow(10, 4 - j) % 10;
      if (n1 != n2)
      {
        tf = false;
        break;
      }
      i1 /= 10;
    }
    if (tf == true)
    {
      N++;
    }
  }
  printf("%d\n", N);
}

int pow(int x, int y)
{
  int z = x;
  for (int i = 0; i < y - 1; i++)
  {
    x *= z;
  }
  return x;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9 + 1
#define int long long
struct item{
	int weight, value;
};
int solve(vector<item> vec, int n, int w){
	
	int maxVal = n * 1000;
	int dp[n + 1][maxVal + 1];
	for(int i = 0; i <= maxVal; i++)dp[1][i] = inf;
	dp[1][0] = 0;
	dp[1][vec[1].value] = vec[1].weight;
	for(int i = 2; i <= n; i++){
		for(int v = 0; v <= maxVal; v++){
			//1 option is that I did not choose the item so the stil dp[i - 1][v]
			dp[i][v] = dp[i - 1][v];
			//if the value of the current item is greater than what we need
			//then skip that item
			if(vec[i].value > v)
				continue;
			//for each value of v we are calculating the min weight in the knapsack required
			dp[i][v] = min(dp[i - 1][v], vec[i].weight+dp[i-1][v - vec[i].value]);
		}
	}
	//now we'll choose the max x such that dp[n][x] is less than equal to w
	int ans = 0;
	for(int i = 0; i <= maxVal; i++){
		if(dp[n][i] <= w)ans = i;
	}
	return ans;
}

signed main()
{
	int n, w;
	cin >> n >> w;
	vector<item> vec(n+1);
	for(int i = 1; i <= n; i++)cin >> vec[i].weight >> vec[i].value;
	cout << solve(vec, n, w);
}

Measured memory_bytes: 81668
#include <cstdio>
#include <cstdint>
#include <vector>
#include <algorithm>

int main() {
  int N;
  int A, B;
  scanf("%d %d %d", &N, &A, &B);

  int a = 0;
  int b = 0;
  int c = 0;
  for (int i = 0; i < N; ++i) {
    int P;
    scanf("%d", &P);
    if (P <= A) {
      ++a;
    } else if (P <= B) {
      ++b;
    } else {
      ++c;
    }
  }
  printf("%d\n", std::min({a, b, c}));
}


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

#define F first
#define S second
#define pb push_back
#define ll long long
#define all(v) (v).begin(),(v).end()
#define endl '\n'

using namespace std;

const int N = 2005;
const int MOD = 1e9 + 7;
const int INF = 2000000000;
const ll INFLL = 1LL * INF * INF;

int a[N], b[N];
ll dp[N][N];
int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % MOD;
            dp[i][j] = (dp[i][j] - dp[i - 1][j - 1] + MOD) % MOD;
            if (a[i] == b[j]) {
                dp[i][j] = (dp[i][j] + 1 + dp[i - 1][j - 1]) % MOD;
            }
        }
    }
    cout << (dp[n][m] + 1) % MOD << endl;
    return 0;
}


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

int main (){ 
    int N;   
    string S;
    cin>>N>>S;
    int Count=0;
    int C=0;
   	for(int i=0; i<N; i++){
        
            if(S[i]=='A'){
                C=1;
                continue;
            }
        
        if(C==1){
            if(S[i]=='B'){
                C=2;
               
                continue;
            }
          	
        }
        if(C==2){
            if(S[i]=='C'){
                C=0;
                
                Count++;
                continue;
            }
          	
        }
      	C=0;
      continue;
        
    } 
    cout<<Count<<endl;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
#define INF 100000000
#define IINF 9999999999999;
using vint = vector<int>;
using ll = long long;
using vll = vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

int search(int a,int b){
    int c = a, d = b;
    while(d){
        c %= d;
        swap(c, d);
    }
    return c;
}

int main(){
    int x,y;
    cin>> x >> y;
    cout << x + y - search(x, y) + 1 << endl;
    return 0;
}


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

#define int long long

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;
using P = pair<int, int>;
using ll=long long;

template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    const int MOD = 1e9+7;

    int x,y;
    cin>>x>>y;
    if(x*2<=y&&y<=x*4&&y%2==0){
        cout<<"Yes"<<endl;
    }
    else cout<<"No"<<endl;
}


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

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

    int n;
    cin >> n;

    vector<int> A(201, 1);
    A[0] = A[1] = 0;

    for(int i = 2; i <= 200; i++){
        if(A[i]){
            for(int j = i + i; j <= 200; j += i){
                A[j] = 0;
            }
        }
    }

    int ans = 0;
    for(int i = 3; i <= n; i += 2){
        int t = 1, t_i = i;
        for(int j = 2; j <= i; j++){
            if(A[j] and !(t_i % j)){
                int cnt = 0;
                while(true){
                    t_i /= j;
                    cnt++;
                    if(t_i % j) break;
                }
                t *= (cnt + 1);
                if(t_i == 1) break;
            }
        }
        if(t == 8){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <map>
#include <set>
#include <vector>

#define maxn 100010

#define conf long long

using namespace std;

long long v[maxn];
map<long long, int> dense;
set<long long> V;
map<long long, long long> reduced, opposite;

int main()
{
    long long maxv = 0;
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i];
        dense[v[i]]++;
        maxv = max(maxv, v[i]);
    }

    for (long long i = 1; i <= 3000; ++i) {
        long long cube = i * i * i;
        if (i <= 1000) {
            for (int j = 1; j <= n; ++j) {
                if (v[j] % cube == 0) {
                    reduced[v[j]] = v[j] / cube;
                }
            }
        } else {
            for (long long j = cube; j <= maxv; j += cube) {
                if (dense.find(j) != dense.end()) {
                    reduced[j] = j / cube;
                }
            }
        }
    }

    maxv = 0;
    dense.clear();
    for (int i = 1; i <= n; ++i) {
        v[i] = reduced[v[i]];
        dense[v[i]]++;
        maxv = max(maxv, v[i]);
    }

    for (long long i = 1; i <= 100000; ++i) {
        long long square = i * i;
        if (i <= 1000) {
            for (int j = 1; j <= n; ++j) {
                if (v[j] % square == 0) {
                    opposite[v[j]] = (v[j] / square) * (v[j] / square) * i;
                }
            }
        } else {
            for (long long j = square; j <= maxv; j += square) {
                if (dense.find(j) != dense.end()) {
                    opposite[j] = (j / square) * (j / square) * i;
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (V.find(v[i]) != V.end()) {
            continue;
        }
        V.insert(v[i]);
        if (v[i] == 1) {
            ans++;
            continue;
        }
        long long op = opposite[v[i]];
        int val1 = dense[v[i]];
        int val2;
        if (dense.find(op) != dense.end()) {
            val2 = dense[op];
            V.insert(op);
        } else {
            val2 = 0;
        }
        ans += max(val1, val2);
    }
    cout << ans;
}


Measured memory_bytes: 24448
#include <bits/stdc++.h>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/algorithm/string/classification.hpp> // is_any_of
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/math/tools/minima.hpp>

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

namespace adaptor = boost::adaptors;
using namespace std;
using boost::math::tools::brent_find_minima;
using boost::irange;
using boost::algorithm::join;
using boost::algorithm::split;
using boost::algorithm::replace_all;
using boost::multiprecision::cpp_int;
using ll = long long;
using P = pair<int, int>;

// TOP

void	Main()
{
	ll	q, h, s, d, n;
	cin >> q >> h >> s >> d >> n;
	ll	one;
	one = min({4 * q, 2 * h, s});
	ll	ans;
	if (2 * one <= d)
		ans = one * n;
	else
		ans = d * (n / 2) + one * (n % 2);
	cout << ans << endl;
}
// END

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

Measured memory_bytes: 256
N = int(input())
TA = [list(map(int,input().split())) for i in range(N)]

vote_T = TA[0][0]
vote_A = TA[0][1]
for i in range(1,N):
  var_T = (vote_T + (TA[i][0]-1)) // TA[i][0]
  var_A = (vote_A + (TA[i][1]-1)) // TA[i][1]
  multiple = max(var_T, var_A)
  vote_T = TA[i][0] * multiple
  vote_A = TA[i][1] * multiple
  
print(vote_T + vote_A)

Measured memory_bytes: 3188
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

const ll limit = ll(1e4);
ll n, m;
string dp[limit + 10];
ll w[] = {0,
          2,
          5,
          5,
          4,
          5,
          6,
          3,
          7,
          6};
vector<ll> a;

string max_s(string s1, string s2) {
    if (s1.size() == s2.size()) return s1 > s2 ? s1 : s2;
    else return s1.size() > s2.size() ? s1 : s2;
}


void solve() {

    dp[0] = ""; // i本使ってできる最大の数
    repone(i, n) dp[i] = "0";
    repone(i, n) {
        rep(j, m) {
            if (i >= w[a[j]]) {
                if (dp[i - w[a[j]]] == "0") continue;
                dp[i] = max_s(dp[i - w[a[j]]] + to_string(a[j]), dp[i]);
            }
        }
    }
    cout << dp[n] << endl;
}

int main() {
    cin >> n >> m;
    a.resize(m);
    rep(i, m) {
        cin >> a[i];
    }
    solve();
    return 0;
}

Measured memory_bytes: 31872
import sys

input = sys.stdin.readline


def main():
    a, b, c, d = map(int, input().split())
    while True:
        c -= b
        if c <= 0:
            print('Yes')
            break
        a -= d
        if a <= 0:
            print('No')
            break


if __name__ == '__main__':
    main()


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

using namespace std; 
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>; 

#define INF 100000000
#define MOD 10007
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

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

  int H,W,h,w;
  cin>>H>>W>>h>>w;
  H-=h;
  W-=w;
  cout<<H*W<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
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; }

int main(){
    int x;
    cin >> x;
    if(x>=30) cout << "Yes" <<endl;
    else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w
using namespace std;

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+9;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int k,s,ans = 0;
	cin >> k >> s;
	for(int i = 0;i <= k;i++){
		for(int j = 0;j <= k;j++){
			int d = s - i - j;
			if(d >= 0 && d <= k) ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n,k;
  cin>>n>>k;
  vll a(n),b(n);
  REP(i,n)cin>>a[i]>>b[i];

  vll r;
  r.push_back(k);
  ll m=(1<<30)-1;
  for(ll i=30-1; i>0; i--){
    if((k>>i)&1){
      //remove 2^i
      ll t=k&(m-(1<<i));

      //add 2^i-1
      t|=(1<<i)-1;
      r.push_back(t);
    }
  }


  ll sz=r.size();
  vll sum(sz);
  REP(i,n){
    REP(j,sz){
      if(r[j]==(r[j]|a[i]))
        sum[j]+=b[i];
    }
  }

  ll ans=0;
  REP(i,sz)ans=max(ans,sum[i]);
  cout<<ans<<endl;

}



Measured memory_bytes: 4772
#include<iostream>
#include<vector>
#include<complex>
#include<algorithm>
using namespace std;

typedef double R;
typedef complex<R> P;
typedef vector<P> G;
#define REP(i, n) for(int i=0;i<(int)n;i++)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;i--)
#define X real()
#define Y imag()
const R EPS = 1e-8;

inline int sig(const R &x){return abs(x)<EPS ? 0 : x > 0 ? 1 : -1;}
inline R  inp(const P &a, const P &b){return (conj(a)*b).X;}
inline R outp(const P &a, const P &b){return (conj(a)*b).Y;}
inline int ccw(const P &s, const P &t, const P &p){return sig(outp(t-s, p-s));}

inline P crosspoint(const P &p1, const P &p2, const P &q1, const P &q2){
	R A = outp(p2-p1, q2-q1), B = outp(p2-p1, p2-q1);
	if(!sig(A) && !sig(B)) return q1;
	return q1 + B/A * (q2 - q1);
}

R area(const G &g){
	R sum = 0;
	REP(i, g.size()) sum += outp(g[i], g[(i+1)%g.size()]);
	return abs(sum/2);
}

G cut(const G &g, const P &p1, const P &p2){
	G res;
	REP(i, g.size()){
		if(ccw(p1, p2, g[i]) >= 0) res.push_back(g[i]);
		if(ccw(p1, p2, g[i]) * ccw(p1, p2, g[(i+1)%g.size()]) < 0)
			res.push_back(crosspoint(g[i], g[(i+1)%g.size()], p1, p2));
	}
	return res;
}

R calc(const G &g, R a){
	R l = 0, r = 3000;
	REP(itr, 40){
		R mid = (l+r)/2;
		if(area(cut(g, P(1, mid), P(0, mid))) < a) l = mid;
		else r = mid;
	}
	return r;
}
int n;
R d, V;
int main(){
	while(cin >> n >> d >> V, n){
		G g;
		REP(i, n){
			R x, y;
			cin >> x >> y;
			g.emplace_back(x, y);
		}
		R ans = 0;
		REP(i, n){
			RREP(i, n) g[i] -= g[0];
			P v = g[1]/abs(g[1]);
			RREP(i, n) g[i] /= v;
			ans = max(ans, calc(g, V/d));
			g.push_back(g[0]); g.erase(g.begin());
		}
		printf("%.11f\n", ans);
	}
	return 0;
}

Measured memory_bytes: 1268
/*
 Shahadat Hossain
 I.C.T Department
 Comilla University
 Session: 2013-2014
 */

#include<iostream>
#include<map>
#include<queue>
#include<vector>
using namespace std;


int main(){
    int n;
    cin >> n;
    
    map<pair<int,int>, vector<pair<int,int> > > S;
    map<pair<int,int>, int> indeg;
    
    
    queue<pair<int,int> > Q;
    
    for(int i = 1 ; i <= n; i++){
        pair<int,int> last;
        for(int j = 1; j < n; j++){
            int u = i;
            int v; cin >> v;
            if(u > v) swap(u, v);

            if(j == 1){
                last = {u, v};
            }
            else{
                S[last].push_back({u, v});
                indeg[{u,v}]++;
                last = {u, v};
            }
        }
    }
    
    for(int i = 1; i <= n; i++)
        for(int j = i + 1; j <= n; j++)
            if(!indeg.count(make_pair(i, j)))
                Q.push({i, j});
               
    int day = 0;
    while(!Q.empty()){
        vector<pair<int,int> > store;
        while(Q.size()){
            store.push_back(Q.front());
            Q.pop();
        }
        for(auto c: store){
            for(auto d: S[c]){
                indeg[d]--;
                if(indeg[d] == 0){
                    Q.push(d);
                    indeg.erase(d);
                }
            }
        }
        day++;
    }
    if(indeg.size() == 0){
        cout << day << endl;
    }
    else{
        cout << -1 << endl;
    }
    
    
}


Measured memory_bytes: 86144
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef long long ll;
typedef long long integer;
//////////////////////////////////////////////////
/* AtCoder Beginner Contest 105 (๑•﹏•๑｀) */

int main(){
	int N; SCD(N);
	bool flg = false;
	FORq(i,0,30){
		FORq(j,0,20){
			if (4*i + 7*j == N){
				flg =true;
			}
		}
	}

	if (flg) printf("Yes\n");
	else printf("No\n");
	return 0;
}

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

int root(int x) { //きりすて
  int OK = 0;
  int NG = x;
  while (NG - OK > 1) {
    int Mid = (OK + NG)/2;
    if (Mid * Mid <= x) {
      OK = Mid;
    }
    else {
      NG = Mid;
    }
  }
  return OK;
}

int main() {
  int N;
  cin >> N;
  vector<int> hp(N);
  for (int i=0; i<N; i++) {
    cin >> hp.at(i);
  }
  sort(hp.begin(),hp.end());
  
  int answer = 1;
  int judge = 0;
  int owari = 0;
  for (int i=0; i<1; i--) {
    judge = 0;
    for (int j=2; j<=hp.at(0);j++) {
      for (int k=0; k<N; k++) {
        if (hp.at(k)%j != 0) {
          break;
        }
        if (k == N-1) {
          for (int l=0; l<N; l++) {
            hp.at(l) = hp.at(l) / j;
          }
          answer = answer * j;
          judge = 1;
          cerr << answer << endl;
          break;
        }
      }
      if (judge == 1) {
        break;
      }
      if (j == hp.at(0)) {
        owari = 1;
        break;
      }
    }
    if (owari == 1) {
      break;
    }
    if (2>min(root(hp.at(N-1)),hp.at(0))) {
      break;
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 640
#include <stdio.h>
int main(void)
{
    int a, b, c, i, j;
    scanf("%d %d %d", &a, &b, &c);
    for (i = a, j = 0; i <= b; i++)
    {
        if (c % i == 0)
        {
            j++;
        }
    }
    printf("%d\n", j);
    return 0;
}


Measured memory_bytes: 2760
import java.io.PrintStream;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {
    static final Scanner     sc = new Scanner(System.in);
    static final PrintStream so = System.out;

    static final int WHITE = 0;
    static final int BLACK = 1;
    static final int INF = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws InterruptedException {
        int n = ni();
        int[] color = new int[n+1];
        boolean[] visited = new boolean[n+1];
        Map<Integer, Map<Integer, Integer>> cost = new HashMap<>();
        
        for (int i = 0; i <= n; i++) {
            cost.put(i, new HashMap<>());
        }
        
        
        for (int i = 0; i < n-1; i++) {
            int ui = ni();
            int vi = ni();
            int wi = ni();
            cost.get(ui).put(vi, wi);
            cost.get(vi).put(ui, wi);
        }
        
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(1);
        color[1] = WHITE;
        
        while (!deque.isEmpty()) {
            Integer first = deque.pollFirst();
            visited[first] = true;
            Map<Integer, Integer> costFromFirst = cost.get(first);
            
            for (Integer next : costFromFirst.keySet()) {
                if (!visited[next]) {
                    deque.addLast(next);
                    color[next] = costFromFirst.get(next) % 2 == 0 ? color[first] : changeColor(color[first]);
                    visited[next] = true;
                }
            }
        }
        
        for (int i = 1; i <= n; i++) {
            so.println(color[i]);
        }
    }
    
    static int changeColor(int color) {
        return color == BLACK ? WHITE : BLACK;
    }
    
    private static int ni() {
        return sc.nextInt();
    }

    private static long nl() {
        return sc.nextLong();
    }

    private static String ns() {
        return sc.next();
    }

    private static char[] nsToChars() {
        return sc.next().toCharArray();
    }

    private static int[] nints(int n) {
        return nints(n, 0);
    }

    private static int[] nints(int n, int padding) {
        int[] a = new int[padding + n];
        for (int i = 0; i < n; i++)
            a[padding + i] = ni();
        return a;
    }
}


Measured memory_bytes: 127624
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt();
		int K = sc.nextInt();
		if (K > N / 2) {
			System.out.println(-1);
			return;
		}
		int[] ord = new int[N];
		int f = 1;
		int b = N - 1;
		ord[0] = 0;
		ord[1] = 1;
		for (int i = 2; i < N; ++i) {
			if (i % 2 == 0) {
				ord[i] = b--;
			} else {
				ord[i] = ++f;
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < K; ++i) {
			for (int j = 0; j < N - 1; ++j) {
				int v1 = (ord[j] + i) % N + 1;
				int v2 = (ord[j + 1] + i) % N + 1;
				sb.append(v1 + " " + v2 + "\n");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

}

Measured memory_bytes: 69000
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int H = scan.nextInt();
        int W = scan.nextInt();
        int N = scan.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scan.nextInt();
        }
        int dx = 1;
        int dy = 1;
        int current = 1;
        for (int i = 0; i < H; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < W; j++) {
                if (i % 2 == 0) {
                    sb.append(current);
                    sb.append(" ");
                    a[current - 1] -= 1;
                } else {
                    sb.insert(0, " ");
                    sb.insert(0, current);
                    a[current - 1] -= 1;
                }
                if (a[current-1] == 0) {
                    current += 1;
                }
            }
            System.out.println(sb.substring(0, sb.length()-1));
        }
    }
}


Measured memory_bytes: 30304
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << (x) << endl
using namespace std;

const int N = 100005, M = 200005;

int n, m, dfn[N], val[N], l[M], r[M], ans[M], cnt = 0;
pair<int, int> vec[N];
vector<pair<int, int> > g[N];
bool vis[N], flag = true;

int dfs (int u) {
	int x = val[u];
	vis[u] = true;
	for (int i = 0; i < g[u].size(); i++) {
		int v = g[u][i].first;
		if (!vis[v]) {
			int y = dfs(v);
			if (y) ans[g[u][i].second] = 1, x ^= 1;
		}
	}
	return x;
}
int main () {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++) scanf("%d%d", &vec[i].first, &vec[i].second);

	sort(vec, vec + n);
	for (int i = 0; i <= n; i++) {
		val[i] = 0;
		if (i < n) val[i] ^= vec[i].second;
		if (i) val[i] ^= vec[i - 1].second;
	}

	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &l[i], &r[i]);
		int pos_l = lower_bound(vec, vec + n, make_pair(l[i], 0)) - vec;
		int pos_r = lower_bound(vec, vec + n, make_pair(r[i] + 1, 0)) - vec;
		if (pos_l == pos_r) continue;
		g[pos_l].push_back(make_pair(pos_r, i));
		g[pos_r].push_back(make_pair(pos_l, i));
	}

	for (int i = 0; i <= n; i++) vis[i] = false;
	for (int i = 1; i <= m; i++) ans[i] = 0;
	for (int i = 0; i <= n; i++) {
		if (!vis[i]) flag &= !dfs(i);
	}

	if (!flag) puts("-1");
	else {
		int k = 0;
		for (int i = 1; i <= m; i++) k += ans[i];
		printf("%d\n", k);
		for (int i = 1; i <= m; i++) {
			if (ans[i]) printf("%d ", i);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
    unsigned long long h, w;
    cin >> h >> w;
    unsigned long long ans = h*w;
    if (h == 1 || w == 1) ans = 1;
    else if(ans%2 == 0) ans /= 2;
    else{
        ans /= 2;
        ans ++;
    }
    cout <<  ans << endl;
}

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

#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

int bpm(int x, unsigned int y) {
  if (x == 0) return 0;
  if (y == 0) return 1;
  int ans   = 1;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  x %= MOD;
  for (unsigned int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) ans = ans * x % MOD;
    x = x * x % MOD;
  }
  return ans;
}

class CTrainTicket {
public:
  static void solve(std::istream &cin, std::ostream &cout) {
    string S;
    cin >> S;
    int A = S[0] - '0', B = S[1] - '0', C = S[2] - '0', D = S[3] - '0';
    string ans;
    if (A + B + C + D == 7) {
      ans = "A+B+C+D=7";
    } else if (A - B + C + D == 7) {
      ans = "A-B+C+D=7";
    } else if (A - B - C + D == 7) {
      ans = "A-B-C+D=7";
    } else if (A - B - C - D == 7) {
      ans = "A-B-C-D=7";
    } else if (A - B + C - D == 7) {
      ans = "A-B+C-D=7";
    } else if (A + B - C + D == 7) {
      ans = "A+B-C+D=7";
    } else if (A + B - C - D == 7) {
      ans = "A+B-C-D=7";
    } else {
      ans = "A+B+C-D=7";
    }
    rep(i, ans.size()) {
      if (ans[i] == 'A') ans[i] = '0' + A;
      if (ans[i] == 'B') ans[i] = '0' + B;
      if (ans[i] == 'C') ans[i] = '0' + C;
      if (ans[i] == 'D') ans[i] = '0' + D;
    }
    cout << ans << endl;
  }
};


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


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

int main(){

	double k,total;
	cin >> total >> k;
	double whole = total,positive=0;
	if(total>=k) positive += total-k+1;
	double chance = 0.5000000000000000000000;
	total = min(total,k);
	if(total == k) total--;
	while(total*2<k) {k=k/2; chance*=0.5;}
	while(total){
		//cout << total << " " << k << endl;
		
		if(total*2 < k){k=k/2;chance*=0.5;}
		//cout << total << " " << k << " " << chance<< endl;
		positive+=chance;
		total--;
		
	}
	cout << setprecision(16) << positive/whole;
		
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

var N int
var x, y, t []int

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

func main() {
	fmt.Scanf("%d", &N)

	x = make([]int, N)
	y = make([]int, N)
	t = make([]int, N)

	for i := 0; i < N; i++ {
		fmt.Scanf("%d %d %d", &t[i], &x[i], &y[i])
	}

	if travel(0) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

func travel(i int) bool {
	if i+1 < N {
		dt, dx, dy := t[i+1]-t[i], Abs(x[i]-x[i+1]), Abs(y[i]-y[i+1])
		if dt >= dx+dy && dt%2 == (dx+dy)%2 {
			return travel(i + 1)
		}
		return false
	}

	return t[0] >= x[0]+y[0] && t[0]%2 == (x[0]+y[0])%2
}

func Abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}


Measured memory_bytes: 12160
######################
# AC: ms(PyPy)
# AC: ms(Python3)
######################

from bisect import bisect_left
import sys
input = sys.stdin.readline


def main():
    N,M = map(int, input().split())
    A = [int(i) for i in input().split()]

    A.sort()

    left = 0
    right = A[-1] * 2 + 5
    while right - left > 1:
        X = (left + right) // 2

        count = 0
        for a in A:
            i = bisect_left(A, X-a)
            count += (N - i)

        if count >= M:
            left = X
        else:
            right = X

    count = 0
    num = []
    append = num.append
    for a in A:
        i = bisect_left(A, left-a)
        count += (N - i)
        append(N - i)

    diff = count - M
    ans = 0
    for i, a in zip(num, A):
        ans += i * a

    print(ans * 2 - diff * left)


if __name__ == "__main__":
    main()


Measured memory_bytes: 58128
#include <iostream>
#include <string>
#include <set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <set>
#include <map>
using namespace std;
#define Max 1000000000
map<string, int> a, b;
int main() {
	string str;
	int n, m;
	while (cin >> n) {
		for (int i = 1; i <= n; ++i) {
			cin >> str;
			a[str]++;
		}
		cin >> m;
		for (int i = 1; i <= m; ++i) {
			cin >> str;
			b[str]++;
		}
		int MAX = 0;
		map<string, int>::iterator it = a.begin();
		for (; it != a.end(); ++it) {
			MAX = max(MAX, a[it->first] - b[it->first]);
		}
		cout << MAX << endl;
		a.clear();
		b.clear();
	}
	return 0;
}

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

inline int gi()
{
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	int sum = 0;
	while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

const int maxn = 100005;

int n, m, a[maxn], b[maxn], p[maxn], fa[maxn], vis[maxn];
long long f[maxn], s[maxn];

struct edge
{
	int to, next;
} e[maxn * 2];
int h[maxn], tot;

inline void add(int u, int v)
{
	e[++tot] = (edge) {v, h[u]}; h[u] = tot;
	e[++tot] = (edge) {u, h[v]}; h[v] = tot;
}

int find(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}

int main()
{
	n = gi(); m = gi();
	for (int i = 1; i <= n; ++i) {
		a[i] = gi(); b[i] = gi();
		a[i] = max(0, a[i] - b[i]);
	}
	for (int i = 1; i <= m; ++i) add(gi(), gi());
	
	for (int i = 1; i <= n; ++i) fa[i] = p[i] = i, s[i] = b[i], f[i] = a[i];

	sort(p + 1, p + n + 1, [](const int &x, const int &y) {return a[x] < a[y];});

	for (int k = 1; k <= n; ++k) {
		int u = p[k];
		vis[u] = 1;
		for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
			if (vis[v]) {
				int x = find(u), y = find(v);
				if (x == y) continue;
				fa[y] = x;
				s[x] += s[y];
				f[x] = min(f[x], max(f[y], a[x] - s[y]));
			}
	}

	int x = find(1);
	printf("%lld\n", f[x] + s[x]);
	
	return 0;
}



Measured memory_bytes: 5760
import sys
import math
#from queue import *
#import random
#sys.setrecursionlimit(int(1e6))
input = sys.stdin.readline
 
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input()))
def inara():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
################################################################
############ ---- THE ACTUAL CODE STARTS BELOW ---- ############

n=inp()
mod=int(1e9+7)

ans=pow(10,n,mod)-(2*pow(9,n,mod)-pow(8,n,mod))
ans%=mod
ans+=mod
ans+=mod
ans%=mod
print(ans)


Measured memory_bytes: 9200
#include<stdio.h>
using namespace std;
int main()
{
	int H, W,X,Y;
	char S[60][60];
	int count[60][60] = { 0 };
	int dx[8] = { 1,1,0,-1,-1,-1,0,1 };
	int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
	scanf("%d%d", &H, &W);
	for (int i = 0; i < H; i++) {
		scanf("%s", S[i]);
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (S[i][j] == '.') {
				for (int k = 0; k < 8; k++) {
					X = i + dx[k];
					Y = j + dy[k];
					if (X<0 || X>=H || Y<0 || Y>=W) {
						
					}
					else {
						if (S[X][Y] == '#') {
							count[i][j]++;
						}
					}
				}
				printf("%d", count[i][j]);
			}
			else if (S[i][j] == '#') {
				printf("#");
			}
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 128
# B  => TLE
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*n
for i in range(1, n):
    a = 10**100
    if i >= k:
        for j in range(1, k+1):
            if a > dp[i-j] + abs(h[i-j]-h[i]):
                a = dp[i-j] + abs(h[i-j]-h[i])
    else:
        for j in range(1, i+1):
            if a > dp[i-j] + abs(h[i-j]-h[i]):
                a = dp[i-j] + abs(h[i-j]-h[i])
    dp[i] = a
    
print(dp[-1])

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

int main(){
  int n; cin >> n;
  map<string,int> mp;
  
  for(int i=0; i<n; ++i){
    string s; cin >> s;
    mp[s]++;
  }
  
  printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d\n",mp["AC"],mp["WA"],mp["TLE"],mp["RE"]);
  return 0;
  
}

Measured memory_bytes: 3712
N, K = map(int, input().split())
H = list(map(int, input().split()))

INF = 10 ** 18

h = H
dp = [0] * N

for n in range(1, N):
	l, r = max(0, n - K), n
	dp[n] = min([dpl + abs(hl - h[r]) for dpl, hl in zip(dp[l:r], h[l:r])])
	#print(dp)
print(dp[N - 1])


Measured memory_bytes: 13980
package main
import "fmt"
func main() {
  var n,a,s int
  fmt.Scan(&n)
  bs := NewBitSet(2000*n)
  for i:=0;i<n;i++ {
    fmt.Scan(&a)
    s += a
    bs.ShiftOr(a)
    bs.Set(a,true)
  }
  for i:=(s+1)/2;i<2000*n+1;i++ {
    if bs.Get(i) { fmt.Println(i);return }
  }
}
type BitSet struct { bits []uint64 }
func NewBitSet(n int) BitSet { return BitSet{make([]uint64,n/64+1)} }
func(b BitSet) Set(idx int,bit bool) {
  i,k := idx/64,idx%64
  if bit { b.bits[i] |= 1<<uint(k);return }
  b.bits[i] &= ^(1<<uint(k))
}
func(b BitSet) Get(idx int) bool {
  i,k := idx/64,idx%64
  return (b.bits[i]>>uint(k))&1 == 1
}
func(b BitSet) ShiftRight(n int) {
  i,k := n/64,n%64
  for x:=0;x<len(b.bits);x++ {
    s := x+i
    if s >= len(b.bits) { b.bits[x] = 0;continue }
    b.bits[x] = b.bits[s]>>uint(k)
    if k > 0 && s+1 < len(b.bits) {
      b.bits[x] |= b.bits[s+1]<<uint(64-k)
    }
  }
}
func(b BitSet) ShiftLeft(n int) {
  i,k := n/64,n%64
  for x:=len(b.bits)-1;x>-1;x-- {
    s := x-i
    if s < len(b.bits) { b.bits[x] = 0;continue }
    b.bits[x] = b.bits[s]<<uint(k)
    if k > 0 && s > 0 {
      b.bits[x] |= b.bits[s-1]>>uint(64-k)
    }
  }
}
func(b BitSet) ShiftOr(n int) {
  i,k := n/64,n%64
  for x:=len(b.bits)-1;x>i;x-- {
    s := x-i
    b.bits[x] |= b.bits[s]<<uint(k)
    if k > 0 { b.bits[x] |= b.bits[s-1]>>uint(64-k) }
  }
  b.bits[i] |= b.bits[0]<<uint(k)
}
func(b BitSet) Or(o BitSet) {
  for i:=0;i<len(b.bits);i++ {
    b.bits[i] |= o.bits[i]
  }
}
func(b BitSet) And(o BitSet) {
  for i:=0;i<len(b.bits);i++ {
    b.bits[i] &= o.bits[i]
  }
}

Measured memory_bytes: 1152