akhauriyash/Code-Regression huggingface dataset:
// vim: shiftwidth=2 expandtab foldmethod=marker

// include {{{
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cmath>
#include <utility>
#include <cstdlib>
#include <random>
#include <chrono>
#include <limits>
// }}}

// debug(...) {{{
#ifdef LOCAL_DEBUG
#include "./debug.h"
#else
bool debug_enabled = false;
#define debug(...)
#define debugn(...)
#define debug_reset()
#endif

// }}}

// bin {{{
template<class T>
std::string bin(int bits, const T& x) {
  char buf[bits + 1];
  buf[bits] = '\0';
  for(int i = 0; i < bits; i++) {
    if((x >> i) & 1) {
      buf[bits - i - 1] = '1';
    } else {
      buf[bits - i - 1] = '0';
    }
  }
  return std::string(buf);
}
std::string bin(int x) {
  if(x < 0) return bin(32, x);
  for(int i = 4; i < 31; i++) {
    int y = 1 << i;
    if(x < y) return bin(i, x);
  }
  return bin(32, x);
}
// }}}

// misc {{{
using namespace std;
template<class T, class U>

using umap = unordered_map<T, U>;
template<class T>
using uset = unordered_set<T>;

typedef long long ll;

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

template<class T>
void sort(T& arr) { // {{{
  std::sort(arr.begin(), arr.end());
} // }}}
template<class T, class By>
void sort_by(T& arr, By by) { // {{{
  std::sort(arr.begin(), arr.end(), [by](auto l, auto r){return  by(l) < by(r); });
} // }}}

template<class T>
void reverse(T& arr) { // {{{
  std::reverse(arr.begin(), arr.end());
} // }}}

class Random { // {{{
  public:
  std::uniform_int_distribution<> uniform_int;
  std::mt19937 rnd;
  std::bernoulli_distribution bern_dist;
  int uniform(int l, int r) {
    return uniform_int(rnd, std::uniform_int_distribution<>::param_type(l, r));
  }
  int next(int N) {
    return uniform(0, N - 1);
  }
  int bern(double p) {
    return bern_dist(rnd, std::bernoulli_distribution::param_type(p));
  }
}; // }}}

template <class A>
ostream& out_vec(const vector<A>& x, const string& sep) { // {{{
  rep(i, x.size()) {
    cout << x[i];
    if(i < x.size() - 1)
      cout << sep;
  }
  return cout;
} // }}}
// }}}

// modulo {{{
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

ll modplus(ll a, ll b, ll mod) {
  ll x = ((a % mod) + (b % mod)) % mod;
  if(x < 0) x += mod;
  return x;
}

ll modminus(ll a, ll b, ll mod) {
  return modplus(a, -b, mod);
}

// }}}

// main {{{
void solve();
int main() {
  cout << setprecision(20);
  solve();
}
// }}}

void solve() {
  int A, B;
  cin >> A >> B;
  int ans = max(0, A - 2 * B);
  cout << ans << endl;
}


Measured memory_bytes: 888
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

int gcd(int a, int b) { return (b == 0) ? a : gcd(b, a % b); }

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(int, n);
    CINS(ll, a, n);

    ll ans, tempSum;

    if ( a[0] > 0 ) {
        ans = 0;
        tempSum = a[0];
    } else {
        ans = fabs(a[0])+1;
        tempSum = 1;
    }

    for (int i = 1; i < n; i++) {
        if ( tempSum > 0 && tempSum + a[i] >= 0 ) {
            ans += fabs(tempSum + a[i]) + 1;
            tempSum = -1;
        } else if ( tempSum < 0 && tempSum + a[i] <= 0 ) {
            ans += fabs(tempSum + a[i]) + 1;
            tempSum = 1;
        } else {
            tempSum += a[i];
        }
    }


    ll ans1 = ans;

    if ( a[0] < 0 ) {
        ans = 0;
        tempSum = a[0];
    } else {
        ans = fabs(a[0])+1;
        tempSum = -1;
    }

    for (int i = 1; i < n; i++) {
        if ( tempSum > 0 && tempSum + a[i] >= 0 ) {
            ans += fabs(tempSum + a[i]) + 1;
            tempSum = -1;
        } else if ( tempSum < 0 && tempSum + a[i] <= 0 ) {
            ans += fabs(tempSum + a[i]) + 1;
            tempSum = 1;
        } else {
            tempSum += a[i];
        }
    }

    cout << min(ans,ans1) << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>

typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep_r(i,s,n)for(ll i = n;i>s;i--)
#define rep_re(i,s,n)for(ll i = n;i>=s;i--)
using namespace std;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;

ll dp[1001][4097];
ll a[1001];
ll c[1001];
int main() {
	ll n, m; cin >> n >> m;
	repe(i, 1, m) {
		ll b;
		cin >> a[i] >> b;
		ll C = 0;
		rep(i, 0, b) {
			ll x; cin >> x;
			C |= 1 << (x - 1);
		}
		c[i] = C;
	}

	ll N = 1; while (n--)N *= 2;
	repe(i, 0, m) repe(j, 0, N) dp[i][j] = INF;
	dp[0][0] = 0;

	rep(i, 0, m)rep(j, 0, N) {
		if (dp[i][j] != INF) {
			//use
			dp[i + 1][j] = min(dp[i][j], dp[i + 1][j]);
			//un use
			dp[i + 1][j | c[i]] = min(dp[i][j] + a[i], dp[i + 1][j | c[i]]);
		}
	}

	ll ans = INF;
	repe(i, 0, m) {
		ans = min(ans, dp[i][N - 1]);
	}

	if (ans == INF) {
		cout << -1 << endl;
	}
	else {
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 32256
#include<bits/stdc++.h>
using namespace std;
#define ull            unsigned long long
#define ll             long long
#define vi             vector<int>
#define umap           unordered_map
#define pb             push_back
#define pii            pair<int,int>
#define vit            vector<int> :: iterator
#define sit            set<int> :: iterator
#define ff             first
#define ss             second
#define endl           '\n'
#define all(x)         x.begin(), x.end()
#define dbg(x)     cerr << #x << " is " << x << endl;
int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};

int main()
{
    string s;
    cin>>s;
    int len=s.size();
    int cnt=0,half=len/2;
    for(int i=0; i<half; i++){
        if(s[i]!=s[len-1-i])cnt++;
    }
    cout<<cnt;
    return 0;
}



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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    ll a, b, c, d;
    cin >> n >> a >> b >> c >> d;
    for (ll i = 0; i <= n - 1; ++i) {
        ll p1 = i * c;
        ll p2 = i * d;
        ll m1 = (n - 1 - i) * c;
        ll m2 = (n - 1 - i) * d;
        ll t1 = a + p1 - m2;
        ll t2 = a + p2 - m1;
        if (b >= t1 && b <= t2) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main() {
	int N, M;
	cin >> N >> M;
	vector<int> H(N);
	for (int i = 0; i < N; i++) cin >> H[i];
	vector<int> Good(N,1);
	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;
		Good[(H[a - 1] < H[b - 1] ? a - 1 : b - 1)] = 0;
		if (H[a - 1] == H[b - 1]) Good[a - 1] = 0;
	}
	int ans = 0; 
	for (int i = 0; i < N; i++) ans += Good[i];
	cout << ans << endl;
}


Measured memory_bytes: 4052
#include<bits/stdc++.h>
#define ll long long int
#define FOR(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n)
using namespace std;

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

  if (a > b) {
    temp = a;
    a = b;
    b = temp;
  }

  if (b > c) {
    temp = b;
    b = c;
    c = temp;
  }

  if (a > b) {
    temp = a;
    a = b;
    b = temp;
  }

  cout << a << " " << b << " " << c << endl;
  return 0;
}

Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
  int N,j=0,k=0;
  cin>>N;
  for(int i=1;i<=N;i++){
    int p;
    cin>>p;
    if(i==p)
      k++;
    else if(k>0){
      j+=(k+1)/2;
      k=0;
    }
  }
  j+=(k+1)/2;
  cout<<j<<endl;
}

Measured memory_bytes: 3580
h, w = map(int, input().split())
def calc(x, y):
  x1 = x // 2
  x2 = x - x1
  ans = min(x % 3, 1) * y
  if x == 2:
    ans = x * y
  for i in range(y):
    s1 = (i + 1) * x
    s2 = (y - i - 1) * x1
    s3 = (y - i - 1) * x2
    s = [s1, s2, s3]
    s.sort()
    cand = s[2] - s[0]
    if cand < ans:
      ans = cand
  return ans

print(min(calc(h, w), calc(w, h)))
         


Measured memory_bytes: 40300
from heapq import *
N, = map(int, input().split())
A = list(map(int, input().split()))
s = sum(A[:N])
rs = [s] + [0] * N
l = []
for i in range(N):
    heappush(l, A[i])
for i in range(N, 2*N):
    s += A[i]
    heappush(l, A[i])
    x = heappop(l)
    s -= x
    rs[i-N+1] = s
l2 = []
s2 = 0
for i in range(2*N, 3*N):
    heappush(l2, -A[i])
    s2+=A[i]

rs2 = [0] * N + [s2]
for i in range(2*N-1, N-1, -1):
    s2 += A[i]
    heappush(l2, -A[i])
    x = -heappop(l2)
#    print(A[i])
#    print(x)
    s2 -= x
    rs2[i-N] = s2
#print(rs2)
r = -10**18
for i in range(N+1):
    c = rs[i] - rs2[i]
    r = max(c, r)
print(r)


Measured memory_bytes: 120592
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for(int i = 0; ; i++) {
            int sum = 0;
            String x = sc.next();
            if(x.equals ("0")) break;
            for(int j = 0; j < x.length(); j++) {
                sum += x.charAt(j) - '0';
            }
            System.out.println(sum);
        }
    }
}


Measured memory_bytes: 26332
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int32_t main(){
	int n, m;
	cin >> n >> m;
	
	char grid[n][m];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			cin >> grid[i][j];
	int dp[n+1][m+1];
	memset(dp,0,sizeof dp);
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(i == 1 && j == 1){
				dp[i][j] = 1;
			}
			else{
				if(grid[i-1][j-1] != '#'){
					dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
				}
			}
		}
	}
	cout << dp[n][m] << endl;
	
	return 0;
}



Measured memory_bytes: 9088
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		List<int>[] E = new List<int>[N];
		for(int i=0;i<N;i++){
			E[i] = new List<int>();
		}
		for(int i=0;i<N-1;i++){
			E[A[i]].Add(B[i]);
			E[B[i]].Add(A[i]);
		}
		
		int[] parent = new int[N];
		var q = new Queue<int>();
		for(int i=0;i<N;i++) parent[i] = -2;
		parent[0] = -1;
		q.Enqueue(0);
		while(q.Count > 0){
			var now = q.Dequeue();
			foreach(var nxt in E[now]){
				if(nxt == parent[now]) continue;
				parent[nxt] = now;
				q.Enqueue(nxt);
			}
		}
		
		long[] add = new long[N];
		for(int i=0;i<Q;i++){
			add[P[i]] += X[i];
		}
		
		long[] sum = new long[N];
		
		q = new Queue<int>();
		q.Enqueue(0);
		while(q.Count > 0){
			var now = q.Dequeue();
			sum[now] += add[now];
			if(parent[now] != -1){
				sum[now] += sum[parent[now]];
			}
			foreach(var nxt in E[now]){
				if(nxt == parent[now]) continue;
				q.Enqueue(nxt);
			}
		}
		Console.WriteLine(String.Join(" ",sum));
		
		
	}
	int N, Q;
	int[] A, B;
	int[] P;
	long[] X;
	public Sol(){
		var d = ria();
		N = d[0]; Q = d[1];
		A = new int[N-1];
		B = new int[N-1];
		for(int i=0;i<N-1;i++){
			d = ria();
			A[i] = d[0] - 1;
			B[i] = d[1] - 1;
		}
		P = new int[Q];
		X = new long[Q];
		for(int i=0;i<Q;i++){
			d = ria();
			P[i] = d[0] - 1;
			X[i] = d[1];
		}
	}

	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}


Measured memory_bytes: 60020
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
using namespace std;
typedef int64_t ll;
typedef vector<ll> vll;typedef pair<ll, ll> pll;typedef vector<vll> vvll;
struct Solution {
    void solve(std::istream& in, std::ostream& out) {
        ll H, W;
        ll N;
        priority_queue<pll> a;
        in >> H >> W;
        in >> N;
        rep(i, N) {
            ll tmp;
            in >> tmp;
            a.push(pll(tmp, i + 1));
        }
        vvll c(H, vll(W));
        while (!a.empty()) {
            pll p = a.top();
            a.pop();
            rep(i, H) {
                if (i % 2) {
                    rep(j, W) {
                        if (!c[i][j]) {
                            c[i][j] = p.second;
                            p.first--;
                        }
                        if (!p.first) break;
                    }
                }
                else {
                    rep(j, W) {
                        if (!c[i][W - j - 1]) {
                            c[i][W - j - 1] = p.second;
                            p.first--;
                        }
                        if (!p.first) break;
                    }
                }
                if (!p.first) break;
            }
        }
        rep(i, H) {
            rep(j, W) {
                out << c[i][j] << ' ';
            }
            out << endl;
        }
    }
};
void solve(std::istream& in, std::ostream& out) {
    out << std::setprecision(12);
    Solution solution;
    solution.solve(in, out);
}
#include <fstream>
#include <iostream>
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    istream& in = cin;
    ostream& out = cout;
    solve(in, out);
    return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

void print_sharpdot(int b)
{
    int a;
    for (a = 1; a <= b / 2; a++)
    {
        printf("#.");
    }
    if (b % 2)
        putchar('#');
}

void print_dotsharp(int b)
{
    int a;
    for (a = 1; a <= b / 2; a++)
    {
        printf(".#");
    }
    if (b % 2)
        putchar('.');
}

void print_Chessboard(int h, int w)
{
    int j;

    for (j = 1; j <= h; j++)
    {
        if (j % 2)
        {
            print_sharpdot(w);
            putchar('\n');
        }
        else
        {
            print_dotsharp(w);
            putchar('\n');
        }
    }
}

int main(void)
{
    int h, w;

    while (1)
    {
        scanf("%d %d", &h, &w);

        if (h == 0 && w == 0)
        {
            break;
        }            
        print_Chessboard(h, w);
        putchar('\n');
    }

    return 0;
}


Measured memory_bytes: 2052
#include<iostream>
#include<stdio.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define MAX 10000

class Data
{
public:
	Data* parent = this;
	int height = 1;
	void Find(Data* other)
	{
		Data* temp = this;
		Data* temp1 = this;
		Data* temp_other = other;
		Data* temp_other1 = other;
		while (1)
		{
			if (temp == temp->parent)break;
			temp = temp->parent;
		}
		//????????§???
		while (temp1!=temp)
		{
			temp1->parent = temp;
			temp1= temp->parent;
		}
		while (1)
		{
			if (temp_other == temp_other->parent) break;
			temp_other = temp_other->parent;
		}
		//????????§???
		while (temp_other1 != temp_other)
		{
			temp_other1->parent = temp_other;
			temp_other1 = temp_other1->parent;
		}
		if (temp == temp_other)cout << 1 << endl;
		else cout << 0 << endl;
	}
	void Unite(Data* other)
	{
		Data* temp = this;
		Data* temp_other = other;
		while (1)
		{
			if (temp == temp->parent)break;
			temp = temp->parent;
		}
		while (1)
		{
			if (temp_other == temp_other->parent) break;
			temp_other = temp_other->parent;
		}
		if (temp_other->height > temp->height)
		{
			temp->parent = temp_other;
		}
		else if (temp_other->height == temp->height)
		{
			temp->parent = temp_other;
			temp_other->height++;
		}
		else
		{
			temp_other->parent = this;
		}
	}
};
int main()
{
	Data data[MAX];
	int n, q;
	cin >> n >> q;
	REP(i, q)
	{
		int com, x, y;
		scanf("%d%d%d",&com,&x,&y);
		if (com == 0)data[x].Unite(&data[y]);
		else
		{
			data[x].Find(&data[y]);
		}
	}
	return 0;
}

Measured memory_bytes: 3376
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	//java11

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int K = sc.nextInt();

		Set<Integer> set = new HashSet<>();
		for(int i=0; i<K; i++) {
			int d = sc.nextInt();

			for(int j=0; j<d; j++) {
				int n = sc.nextInt();
				set.add(n);
			}
		}

		System.out.println(N - set.size());

	}

}


Measured memory_bytes: 46140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10, mod = 1e9 + 7;
 
ll a[N];
int n;
 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    ll ans = 0;
    for (ll i = 0; i < 60; i++) {
        ll numzero = 0, numone = 0;
        for (ll j = 1; j <= n; j++) {
            if ((1LL << i) & a[j]) numone++;
            else numzero++;
        }
        //ans = (ans % mod + 1LL * (numzero * numone % mod)  * (1LL << i) % mod) % mod;
        ans = (ans % mod + (1LL * (numone * numzero) % mod * ((1LL << i) % mod)) % mod) % mod;
    }
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 2560
from operator import itemgetter
n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(n)]
abab.sort(key=itemgetter(0))
y = h = 0
for a, b in abab :
    if h+b < m : y+=a*b ; h+=b
    elif h < m <= h+b : y+=a*(m-h) ; print(y) ; break

Measured memory_bytes: 28968
#include <bits/stdc++.h>
using namespace std;
#define  ll  long long
#define  pb   push_back
#define  ll   long long
#define  mk   make_pair
#define  msi  map<string,int>
#define  mii  map<int,int>
#define  pii  pair<int,int>
int main()
{
    int t,i,j,n,m;
    cin>>n>>m;
    if(n<1 || n>9 || m<1 || m>9)
    {
        cout<<"-1\n";
    }
    else
    {
        cout<<n*m<<"\n";
    }
    return 0;
}


Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define uint unsigned int
#define ull  unsigned long long
typedef string str;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef map<int, int> mii;
typedef vector<int> vi;
typedef vector<bool> vb;
#define pb push_back
#define fi first
#define se second
#define in insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
const int INF = 1e9 + 5;
const int N = 2e5 + 123;
int main(){
    speed;
    int n;
    cin >> n;
    cout << (1000 - n % 1000) % 1000;
}

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

using namespace std;

#define ll long long
#define ini(arr, val) memset(arr, (val), sizeof(arr))
#define loop(i,n)  for(ll i=0; i<n; i++)
#define loop1(i,n)  for(ll i=1; i<=n; i++)

#define all(a)      (a).begin(),(a).end()
#define exist(s,e)  (s.find(e)!=s.end())
#define dbg(x)  cout << #x << " = " << x << endl
#define pt(x) cout<<x<<"\n"
#define pts(x) cout<<x<<" "

#define mp make_pair
#define pb push_back
#define F first
#define S second


#define inf (int)1e9
#define infll 1e18
#define eps 1e-9
#define PI 3.1415926535897932384626433832795
#define mod 1000000007


#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define test   int t; cin>>t; while(t--)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef map<int,int> mii;
typedef set<int> si;

typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<pll> vpll;
typedef vector<vl> vvl;
typedef map<ll,ll> mll;
typedef set<ll> sl;


int dirx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int diry[] = { -1, 0, 1, -1, 1, -1, 0, 1 };



//===========================DEBUG======================//
#define XOX 1
vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

//================================================================//



//////////////////////////////////////////////////////////////////////////////////////////
//                      main starts
//////////////////////////////////////////////////////////////////////////////////////////
int const lmt=2e5+5;


int main(){
    #ifndef ONLINE_JUDGE
    freopen("../input.txt", "r", stdin);
    freopen("../output.txt", "w", stdout);
	#endif
    fast

    ll n,w; cin>>n>>w;
    ll wt[n+1],v[n+1],dp[w+1][2]={0};
    loop1(i,n)cin>>wt[i]>>v[i];

    int flag=0;
    loop(j,n+1){
    	loop(i,w+1){
	    	ll &ret = dp[i][flag]=0;
	    	if(i==0 || j==0)continue;
	    	if(wt[j]<=i)ret=v[j] + dp[i-wt[j]][1-flag];

	    	ret = max(ret, dp[i][1-flag]);
    	}
    	flag = 1-flag;
    }
    // ll ans=0;
    // loop1(i,n)ans = max(ans,dp[w][i]);
    pt(dp[w][1-flag]);
}


/*


*/





Measured memory_bytes: 5208
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;

typedef pair<long long int, long long int> P;
long long int INF = 1e18;

// DP[i][j] : ｉ番目までのコインを使って、ｊ円支払うときの最小の枚数
long long int DP[21][51000];

int main(){
	
	int n, m;
	cin >> n >> m;
	
	int c[21];
	for(int i = 0; i < m; i++){
		cin >> c[i];
	}
	
	
	for(int i = 0; i <= m; i++){
		for(int j = 0; j <= n; j++){
			DP[i][j] = INF;
		}
		DP[i][0] = 0;
	}
	
	for(int i = 0; i < m; i++){
		for(int j = 0; j <= n; j++){
			if(j < c[i]){
				DP[i + 1][j] = DP[i][j];
			}else{
				DP[i + 1][j] = min(DP[i][j], DP[i + 1][j - c[i]] + 1);
			}
		}
	}
	
	cout << DP[m][n] << endl;
	
	return 0;
}


Measured memory_bytes: 11376
#define rep(i, a, b) for(int i = a; i < (int)(b); i++)
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
template<class T> inline void chmax(T &a, const T &b) {if(a < b) a = b;}
template<class T> inline void chmin(T &a, const T &b) {if(a > b) a = b;}
const long long INF = 1LL<<60;
const long long MOD = (ll)1e9+7;
// const long long MOD = (ll)1e6+3;
const long long MAX = (ll)1e5+10;

long long GCD (long long C, long long D) {
   while (1) {
      if (C == 0 || D == 0) break;
      if (D>C) D -= (D/C)*C;
      else C -= (C/D)*D;
   }
   return max(C,D);
}

long long LCM(long long C, long long D) {
   return C / GCD(C,D) * D;
}

int main(void) {
   ll A,B;
   cin>>A>>B;
   cout<<LCM(A,B)<<endl;
   return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<n;i++)
#define For(i,n1,n2) for(int i=n1;i<n2;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define RREP(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
typedef long long ll;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

int main(){
    int n,m,c;
    cin >> n >> m >> c;
    vector<int> b(m);
    REP(i,m){
        cin >> b[i];
    }
    vector<vector<int>> a(n,vector<int>(m,0));
    REP(i,n){
        REP(j,m){
            cin >> a[i][j];
        }
    }
    int res = 0;
    REP(i,n){
        int temp = c;
        REP(j,m){
            temp += a[i][j]*b[j];
        }
        if(temp>0)res++;
    }
    put(res);
    return 0;
}


Measured memory_bytes: 256
<?php

fscanf(STDIN,"%d",$n);
$p = preg_split("/ /",trim(fgets(STDIN)));



//pの文字列と比較する文字列
for ($i = 0; $i < $n; $i++){
    if(($i + 1) != $p[$i]){
        $num++;
    }
}

if ($num == 0 || $num == 2){
    echo "YES";
}else{
    echo "NO";
}


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

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)cin >> a[i];
    int ret = 0;
    for (int i = 0; i < n; i++) {
        bool flag = true;
        for (int j = 0; j < i; j++) {
            if (a[i] < a[j])flag = false;
        }
        if (flag)ret++;
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, x, y;

int main(){
  cin >> n;
  pair<int, int> p[n];
  int a[n];
  for ( int i = 0; i < n; i++){
    cin >> x >> y;
    p[i] = make_pair(x,y);
    a[i] = i;
  }
  long double sum = 0;
  int cnt = 0;
  do {
    cnt ++;
    for ( int i = 1; i < n; i++){
      sum += sqrt(pow(p[a[i]].first - p[a[i-1]].first, 2) + pow(p[a[i]].second-p[a[i-1]].second,2));
    }
;  }while(next_permutation(a, a+n));

  cout << fixed << setprecision(10) << sum/cnt << endl;
  return 0;
}


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

int main() {
	int k;
	cin >> k;
	int64_t a[k];
	for (auto &i : a) {
		cin >> i;
	}
	reverse(a, a + k);
	int64_t l = 2, r = 2;
	for (auto &i : a) {
		int64_t x = (l + i - 1) / i;
		int64_t l_ = i * x;
		int64_t y = r / i;
		int64_t r_ = i * y + i - 1;
		if (l_ > r_) {
			cout << -1 << endl;
			return 0;
		}
		l = l_;
		r = r_;
	}
	cout << l << ' ' << r << endl;
	return 0;
}

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

int main() {
  int n,q;
  cin >> n >> q;
  vector<vector<int>> to(n);
  rep(i,n-1){
      int x,y;
      cin >> x >> y;
      x--;y--;
      to[x].push_back(y);
      to[y].push_back(x);
  }
  queue<int> que;
  que.push(0);
  vector<int> cnt(n,0);
  vector<int> ans(n,-1);
  rep(i,q){
      int x,y;
      cin >> x >> y;
      x--;
      cnt[x]+=y;
  }
  while(!que.empty()){
      int x=que.front();que.pop();
      for(int y:to[x]){
          if(ans[y]!=-1) continue;
          que.push(y);
          cnt[y]+=cnt[x]; 
      }
      ans[x]++;
  }
  rep(i,n) cout << cnt[i] << endl;
}

Measured memory_bytes: 17372
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

int n;
string s[5];

void print_map(){
    cout << "------" << endl;
    rep(i,n) cout << s[i] << endl;
    cout << "------" << endl;
}

pi get_state(){
    int mask = 0;
    int pos = -1;
    rep(i,n)rep(j,n){
        int idx = i*n+j;
        if(s[i][j]=='#') mask |= 1<<idx;
        if(s[i][j]=='@') pos = idx;
    }

    assert(pos!=-1);
    return {pos,mask};
}

void make_state(int pos, int mask){
    rep(i,n)rep(j,n){
        int idx = i*n+j;
        if(mask>>idx&1) s[i][j] = '#';
        else if(idx == pos) s[i][j] = '@';
        else s[i][j] = '.';
    }
}

bool move(int y, int x){
    if(s[y][x] == '#') return false;

    rep(i,n)rep(j,n)if(s[i][j]=='@') s[i][j]='.';
    s[y][x] = '@';
    return true;
}

void infect(){
    string t[5];
    rep(i,n) t[i]=s[i];

    rep(i,n)rep(j,n){
        if(t[i][j]=='@') s[i][j]='@';
        else{
            int ct = 0;
            for(int dy=-1; dy<=1; ++dy)for(int dx=-1; dx<=1; ++dx){
                if(dy==0 && dx==0) continue;

                int y = i+dy, x = j+dx;
                if(0<=y && y<n && 0<=x && x<n) ct += (t[y][x]!='.');
            }

            if(t[i][j]=='#'){
                if(ct==2 || ct==3) s[i][j] = '#';
                else s[i][j] = '.';
            }
            else{
                if(ct==3) s[i][j] = '#';
                else s[i][j] = '.';
            }
        }
    }
}

unordered_map<int,int> dp[25];
int solve(){
    rep(i,25) dp[i].clear();

    pi start = get_state();
    if(start.se==0) return 0;

    queue<pi> que;
    que.push(start);
    dp[start.fi][start.se] = 0;
    while(!que.empty()){
        pi now = que.front();
        que.pop();
        int pos = now.fi, mask = now.se;
        if(mask == 0) return dp[pos][mask];

        // make_state(pos,mask);
        // dbg(dp[pos][mask]);
        // print_map();

        int py = pos/n, px = pos%n;

        for(int dy=-1; dy<=1; ++dy)for(int dx=-1; dx<=1; ++dx){
            if(dy==0 && dx==0) continue;

            int ny = py+dy, nx = px+dx;
            if(0<=ny && ny<n && 0<=nx && nx<n){
                make_state(pos,mask);

                if(move(ny,nx)){
                    infect();
                    pi nxt = get_state();
                    if(!dp[nxt.fi].count(nxt.se)){
                        if(nxt.se == 0) return dp[pos][mask]+1;

                        dp[nxt.fi][nxt.se] = dp[pos][mask]+1;
                        que.push(nxt);
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    while(cin >>n,n){
        rep(i,n) cin >>s[i];
        cout << solve() << endl;
    }
    return 0;
}



Measured memory_bytes: 3448
#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
#include <algorithm>

//0-indexed overflow-> max:Height*MOD sum's comment out:2*MOD
template <class T, int SIZE, T MOD>
struct BinaryIndexedTree {
    T seg[SIZE];
    
    inline void init() {
        fill_n(seg, SIZE, 0);
    }

    inline void add(uint i, T x) {
        while (i < SIZE) {
            seg[i] += x;
            //if (MOD) seg[i] %= MOD;
            i += (i+1) & ~i;
        }
    }
    //[0, i)
    inline T sum(uint i) {
        T s = 0;
        uint d = 1;
        while (i >= d) {
            i -= d;
            s += seg[i];
            //if (MOD) s %= MOD;
            d = (i+1) & ~i;
        }
        //if (MOD) s = (s % MOD + MOD) % MOD;
        return s;
    }
    //[a, b)
    inline T sum(uint a, uint b) {
        T d = sum(b) - sum(a);
        /*if (MOD) {
            d = (d + MOD) % MOD;
        }*/
        return d;
    }
};
const int MN = 100010;
BinaryIndexedTree<ll, MN, 0> b;
ll a[MN];
int main() {
    b.init();
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n-1; i++) {
        scanf("%lld", a+i);
        a[i] %= 100000;
    }
    int u = 0;
    for (int i = 0; i < m; i++) {
        int c;
        scanf("%d", &c);
        int u1 = u, u2 = u+c;
        u = u2;
        if (u1 > u2) swap(u1, u2);
        b.add(u1, 1);
        b.add(u2, -1);
    }
    ll r = 0;
    for (int i = 0; i < n-1; i++) {
        r += b.sum(i+1)*a[i];
        r %= 100000;
    }
    printf("%lld\n", r);
    return 0;
}

Measured memory_bytes: 2772
#include <bits/stdc++.h>
using namespace std;
#define arep(i, x, n) for (int i = int(x); i < (int)(n); i++)
#define rep(i, n) for (long long i = 0; i < n; ++i)
#define pi 3.141592653589793
#define eps 0.00000001
#define INF 1e9 + 7
using ll = long long;

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

    int B[m];
    rep(i, m){
        cin >> B[i];
    }

    int A[n][m];
    rep(j, n){
        rep(i, m){
            cin >> A[j][i];
        }
    }

    int cnt = 0;
    rep(j, n){
        int sum = c;
        rep(i, m){
            sum += B[i] * A[j][i];
        }

        if(sum > 0){
            cnt = cnt + 1;
        }
    }

    cout << cnt << endl;
}

Measured memory_bytes: 3548
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define modulo 1000000007
#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
int main(){
	fast_io;
	string s;
	cin>>s;
    sort(s.begin(),s.end());
    if(s[0]==s[1] && s[2]==s[3] && s[1]!=s[2])
        cout<<"Yes\n";
    else
        cout<<"No\n";
	return 0;
}

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

int main(){
    int n,cnt = 0;
    string s;
    cin >> n >> s;
    for(int i = 0;i < n-2;i++){
        if(s[i] == 'A'){
            if(s[i + 1] == 'B'){
                if(s[i + 2] == 'C'){
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
ll p[100005];
void seive()
{
	memset(p,0,sizeof(p));
	p[1]=1;
	for(ll i=2;i*i<100005;i++)
	{
		if(p[i])continue;
		for(ll j=i*i;j<100005;j+=i)
		{
			p[j]=1;
		}
	}
	return ;
}

int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
 	seive();
   	ll n;
   	cin>>n;
   	for(ll i=n;i<100005;i++)
   	{
   		if(i>=n && !p[i])
   		{
   			cout<<i<<endl;
   			return 0;
   		}
   	}
    return 0;
}

Measured memory_bytes: 1024
N = int(input())
T=[int(input()) for _ in range(N)]
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd(a, b)
if N>1:
    ans = lcm(T[0], T[1])
    for i in range(2,N):
        ans = lcm(ans, T[i])
else:
    ans=T[0]
print(ans)

Measured memory_bytes: 3064
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  def sum(self,i):
    s=0
    while i>0:
      s+=self.tree[i]
      i-=i&-i
    return s

  def add(self,i,x):
    while i<=self.size:
      self.tree[i]+=x
      i+=i&-i

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

for i in range(q):
  print(ans[i])

Measured memory_bytes: 231380
#include <cstring>
#include <cstdio>

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }

const int _ = 200;

int n, m, s[_][_], dp[2][_][_][_]; char a[_][_];

inline int chk(int x1, int y1, int x2, int y2) {
    int res = s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    return res == (y2 - y1 + 1) * (x2 - x1 + 1) || res == 0;
}

inline int bs(int c, int i, int j, int k) {
    int l = i, r = j - 1, res = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        res = max(res, min(dp[c][i][mid][k], dp[c][mid + 1][j][k]));
        if (dp[c][i][mid][k] < dp[c][mid + 1][j][k]) r = mid - 1; else l = mid + 1;
    }
    return res;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (a[i][j] == '#');
    if (chk(1, 1, n, m)) { puts("0"); return 0; }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j)
            for (int l, k = 1; k <= m; k = l) {
                l = k;
                while (l <= m && chk(i, k, j, l)) ++l;
                for (int x = k; x < l; ++x) dp[0][i][j][x] = l - 1;
                if (k == l) dp[0][i][j][k] = k - 1, ++l;
            }
    for (int x = 1; ; ++x) {
        int c = x & 1, c_1 = c ^ 1;
        for (int i = 1; i <= n; ++i)
            for (int j = i; j <= n; ++j)
                for (int k = 1; k <= m; ++k) {
                    int x = dp[c_1][i][j][k];
                    if (x == m) dp[c][i][j][k] = m;
                    else dp[c][i][j][k] = max(dp[c_1][i][j][x + 1], bs(c_1, i, j, k));
                }
        if (dp[c][1][n][1] == m) { printf("%d\n", x); return 0; }
    }
    return 0;
}


Measured memory_bytes: 61568
#include <bits/stdc++.h>
#include <ctime>
#include <sstream>
#define weewoo ios::sync_with_stdio(false);cin.tie(0)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ld long double
#define ll long long
#define se second
#define fi first
#define ctoi(x) (x-'0')
#define pi (acos(-1))
#define llputin(a,n) for(int i=0;i<n;i++){ll x;cin >> x;a.push_back(x);}
#define iputin(a,n) for(int i=0;i<n;i++){int x;cin >> x;a.push_back(x);}

#define MOD ((ll) 1e9 + (ll) 7)
using namespace std;

ll pw(ll x,ll a){
    if(a==0)
        return 1;
    ll t = pw(x,a/2);
    if(a%2==0)
        return (t*t);
    else
        return (t*t*x);
}

bool prime(int x)
{
    if(x < 2) return false;
        for(int i=2; i<= sqrt(x); i++) {
            if ((x%i) == 0) return false;
        }
    return true;
}

set<int>a;

int main()
{
    weewoo;
    ll n;
    cin >> n;
    if(prime(n)){
        cout << n << endl;
        return 0;
    }
    for(int i=2;i<=1e5+7;i++){
        if(prime(i))
            a.insert(i);
    }
    cout << *upper_bound(a.begin(),a.end(),n);
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int h, w; cin >> h >> w;
  VV<> c; assign(c, h, w);
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) cin >> c[i][j];
  int res = 0;
  for (int jl = 0; jl < w; ++jl) {
    V<> a(h);
    for (int i = 0; i < h; ++i) {
      int j = jl;
      while (j < w and !c[i][j]) ++a[i], ++j;
    }
    V<> l(h), r(h);
    stack<int> st;
    st.push(0);
    for (int i = 1; i < h; ++i) {
      while (!st.empty() and a[st.top()] >= a[i]) st.pop();
      l[i] = !st.empty() ? a[i] * (i - st.top() - 1) : a[i] * i;
      st.push(i);
    }
    stack<int>().swap(st);
    st.push(h - 1);
    for (int i = h - 2; i >= 0; --i) {
      while (!st.empty() and a[st.top()] >= a[i]) st.pop();
      r[i] = !st.empty() ? a[i] * (st.top() - 1 - i) : a[i] * (h - 1 - i);
      st.push(i);
    }
    for (int i = 0; i < h; ++i) res = max(res, l[i] + a[i] + r[i]);
  }
  cout << res << '\n';
}


Measured memory_bytes: 10424
from heapq import heappop, heappush
from collections import Counter

N, M, K = list(map(int, input().split()))
G = [[] for _ in range(N)]
deg = [0 for _ in range(N)]
reds = [[] for _ in range(N)]

for _ in range(M):
    _a, _b = list(map(int, input().split()))
    _a -= 1
    _b -= 1
    G[_a].append(_b)
    G[_b].append(_a)
    deg[_a] += 1
    deg[_b] += 1


# compute connected components
numbers = {i: None for i in range(N)}

def dfs():
    visited = [False for _ in range(N)]
    stack = []
    for i in range(N):
        if not visited[i]:
            stack.append(i)
            while len(stack) > 0:
                v = stack.pop()
                visited[v] = True
                numbers[v] = i
                for neighbor in G[v]:
                    if not visited[neighbor]:
                        stack.append(neighbor)
dfs()

for _ in range(K):
    _c, _d = list(map(int, input().split()))
    _c -= 1
    _d -= 1
    if numbers[_c] == numbers[_d]:
        reds[_c].append(_d)
        reds[_d].append(_c)

counter = {}
for i in range(N):
    if numbers[i] not in counter:
        counter[numbers[i]] = 1
    else:
        counter[numbers[i]] += 1

for i in range(N):
    v = counter[numbers[i]] - len(G[i]) - len(reds[i]) - 1
    print(v, end='')
    if i < N - 1:
        print(" ", end='')
print()

Measured memory_bytes: 123304
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}


int main() {
  ll n; cin >> n;
  Vll a(n);
  rep(i, n) cin >> a[i];
  sort(all(a));

  ll ans = 0;
  Vll b(n);
  rep(i, n) {
    b[i] = (a[i] - a[0]) / (n+1);
    ans += b[i];
  }
  rep(i, n) a[i] += (ans - b[i]) - b[i] * n;
  sort(all(a));

  ll dif = a[0] - n;
  if (dif > 0) {
    rep(i, n) a[i] -= dif;
    ans += dif * n;
  }
  
  while (*max_element(all(a)) > n-1) {
    ans++;
    int i = max_element(all(a)) - a.begin();
    rep(j, n) {
      if (j == i) a[j] -= n;
      else a[j]++;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  map<string,int> mp;
  rep(i,n){
    string s;
    cin >> s;
    mp[s]++;
  }
  int mx = 0;
  for(auto p:mp) mx = max(mx,p.second);
  for(auto p:mp){
    if(p.second!=mx) continue;
    cout << p.first << endl;
  }
}


Measured memory_bytes: 25216
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
int main(){
	int n,i;
	char c;
	string s,t;
	for(;cin>>n,n;){
		getline(cin,s);
		map<char,map<string,int> >m;
		for(i=0;i<n;i++){
			string s,t;
			getline(cin,s);
			istringstream is(s);
			for(;is>>t;)m[t[0]][t]--;
		}
		cin>>c;
		vector<pair<int,string> >v;
		map<string,int>::iterator it=m[c].begin();
		for(;it!=m[c].end();it++)
			v.push_back(make_pair(it->second,it->first));
		sort(v.begin(),v.end());
		if(v.empty())cout<<"NA"<<endl;
		else{
			for(i=0;i<5&&i<v.size();i++){
				if(i)cout<<' ';
				cout<<v[i].second;
			}
			cout<<endl;
		}
	}
}

Measured memory_bytes: 952
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define endl '\n'
#define inf 9223372036854775807
#define maxn 3000001
#define mod (ll)(1e9+7)
#define int ll
 
using namespace std;
 
void io(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}

int t,n,d,l,r,k;
int vis[maxn];


int32_t main(){
io();
IOS;    
		cin>>k;
		int num=0;
		int ans=0;
		while(1){
			num=num*10+7;
			num%=k;
			ans++;
			if(num%k==0){
				cout<<ans<<endl;
				return 0;
			}else if(vis[num%k]==1){
				cout<<-1<<endl;
				return 0;
			}
			vis[num%k]=1;
		}

       



        

        


        
    
        
        
                


 
        
 
 
 
        
 
 
 
 
        
        
 
        
        
 
    
    
    
    
 
 
       
 
 
 
 
      
   
 
 
 
 
}

Measured memory_bytes: 11420
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<stack>
#include<string>

using namespace std;
const int INF = 1<<30;
typedef long long int ll;

int calc(int num){
	int d=0;
	while(num!=0){
		d+=num%10;
		num/=10;
	}
	return d;
}

int main(){
	int n;cin>>n;int ans=INF;
	for(int i=1;i<n;i++){
		ans=min(ans, calc(i)+calc(n-i));
	}
	cout << ans << endl;
}

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

void answer1() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N, K;
  cin >> N >> K;
  long long int ans = K * pow(K - 1, N - 1);
  cout << ans << endl;
}

int main() {
  answer1();
}


Measured memory_bytes: 384
h, w, k = map(int, input().split())

dp = [[0 for i in range(w)] for j in range(h+1)]
num = [[0 for i in range(w)] for j in range(w)]


if w == 1:
    num[0][0] = 1
elif w == 2:
    num[0][0] = 1
    num[0][1] = 1
    num[1][0] = 1
    num[1][1] = 1
else:
    for i in range(2 ** (w - 1)):
        for j in range(w - 2):
            if (((i >> j) & 1) == 1) and (((i >> (j + 1)) & 1) == 1):
                break
        else:
            for j in range(w):
                if j == 0:
                    if ((i >> j) & 1) == 1:
                        num[j][j + 1] += 1
                    else:
                        num[j][j] += 1
                elif j == w - 1:
                    if ((i >> (j - 1)) & 1) == 1:
                        num[j][j - 1] += 1
                    else:
                        num[j][j] += 1
                else:
                    if ((i >> j) & 1) == 1:
                        num[j][j + 1] += 1
                    elif ((i >> (j - 1)) & 1) == 1:
                        num[j][j - 1] += 1
                    else:
                        num[j][j] += 1

dp[0][0] = 1
mod = 10**9 + 7
for i in range(h):
    for j in range(w):
        for l in range(w):
            dp[i+1][j] += dp[i][l] * num[l][j]
            dp[i+1][j] %= mod

print(dp[h][k-1])


Measured memory_bytes: 3188
def main():
    n = int(input())
    S = sorted([list(input()) for i in range(n)], key = lambda x : len(x))
    common = [[False for i in range(len(X))] for X in S]

    ref = S[0]
    ans = list()
    for i in range(len(ref)):

        is_common = True
        for j in range(1, len(S)):
            
            find = False
            for k in range(len(S[j])):
                if S[j][k] == ref[i] and common[j][k] == False:
                    common[j][k] = True
                    find = True
                    break

            is_common &= find

        if is_common:
            ans.append(ref[i])

    print("".join(sorted(ans)))

if __name__ == "__main__":
    main()

Measured memory_bytes: 9252