akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> pi;
typedef vector<int> vi;
#define ST first
#define ND second
#define PB push_back
#define DET(a,b,c) (LL(b.x-a.x)*LL((c.y-a.y))-LL((c.x-a.x))*LL((b.y-a.y)))

const int MAXN = 100*1000+10;
int n,w;
int items[101][2];
LL sack[MAXN];
LL ans;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>w;
    for(int i=1; i<=n;i++) cin>>items[i][0]>>items[i][1];
    for(int i=1; i<=w;i++) sack[i]=-1;
    for(int i=1; i<=n;i++) {
        for(int j = w; j>=0;j--) {
            if(j+items[i][0]>w) continue;
            if(sack[j]==-1) continue;
            sack[j+items[i][0]] = max(sack[j+items[i][0]],sack[j] + items[i][1]);
            ans = max(ans,sack[j+items[i][0]]);
        }
    }
    cout<<ans;
}


Measured memory_bytes: 1024
import java.util.Scanner;

class Main{
     public static void main(String[] args){
	//???????????\???
    	Scanner scan = new Scanner(System.in);
	//???????????´??°?????????????????£??\
    	int n = scan.nextInt();
	//boolean??????????´???°???[4][13]??¨??????
    	boolean[][] cards = new boolean[4][13];
    	String s = null;
    	int num;
    	
	//????????????????????°???????????????
    	for(int j = 0; j < 4; j++){
    		for(int i = 0; i < 13; i++){
    			cards[j][i] = false;
    		}
    	}
    	//n?????????????????????s?????????????????£???????????????????????????true?????£??\
    	for(int i = 0; i < n; i++){
    		s = scan.next();
    		num = scan.nextInt();
    		num--;
    		
    		
    		switch(s){
    			case "S":
    				cards[0][num] = true;
    				break;
    			case "H":
    				cards[1][num] = true;
    				break;
    			case "C":
    				cards[2][num] = true;
    				break;
    			case "D":
    				cards[3][num] = true;
    				break;
    		}
    	}
    	
	//????????????????????°??????????????????false????????????????????????
    	for(int j = 0; j < 4; j++){
    		for(int i = 1; i < 14; i++){
    			if(cards[j][i - 1] == true){   				
    			}else{
    				switch(j){
    				  case 0:
    					  s = "S";
    					  break;
    				  case 1:
    					  s = "H";
    					  break;
    				  case 2:
    					  s = "C";
    					  break;
    				  case 3:
    					  s = "D";
    					  break;
    				}   				
    				System.out.println(s + " " + i);
    			}
    			
    		}
    	}
     }
}

Measured memory_bytes: 26144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;

int h, w, ans=0;
vector<vector<bool>> seen;
vector<vector<int>> path;
vector<vector<char>> g;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

// void dfs(int x, int y, int k=0){
//     seen[x][y] = true;
    
//     for(int i=0; i<4; i++){
//         int nx=x+dx[i], ny=y+dy[i];
//         if(nx<0 || ny<0 || h<=nx || w<=ny) continue;
//         if(g[nx][ny]=='#' || seen[nx][ny]) continue;
//         dfs(nx, ny, k+1);
//     }
//     //cout << endl;
// }


int main(){
    cin >> h >> w;
    g.resize(h, vector<char>(w));
    
    for(int i=0; i<h; i++)
        for(int j=0; j<w; j++)  cin >> g[i][j];
  
    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            if(g[i][j]=='#') continue;
            path.assign(h, vector<int>(w, -1));
            queue<pair<int, int>> que;
            que.push({i, j});
            path[i][j] = 0;
            while(!que.empty()){
                int x=que.front().first, y=que.front().second;
                que.pop(); 
                for(int i=0; i<4; i++){
                    int nx = x+dx[i], ny = y+dy[i];
                    if(nx<0 || ny<0 || h<=nx || w<=ny) continue;
                    if(g[nx][ny]=='#' || 0<=path[nx][ny]) continue;
                    path[nx][ny] = path[x][y] + 1;
                    que.push({nx, ny});
                }
            }
            for(int k=0; k<h; k++){
                for(int l=0; l<w; l++){
                    if(g[k][l]=='#') continue;
                    
                    ans = max(ans, path[k][l]);
                }
            }
        }
    }
    cout << ans << endl;

}

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

int main(){
	int H,N;
	cin>>H>>N;
  	vector <int> A(N);
  	for(int i=0; i<N; ++i) cin>>A[i];
  	int sum = accumulate(A.begin(), A.end(), 0);
  	if(sum>=H)cout<<"Yes"<<endl;
  	else cout<<"No"<<endl;
}


Measured memory_bytes: 3792
#include<bits/stdc++.h>
// __builtin_ctz : no of trailing zeros
// in fenwick always use size as 1000010
#define int long long
#define ll long long
#define pp pair<int,int>
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define sa(a,n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a,n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;
int max(int x, int y)
{
    return x>y ? x : y;
}
int min(int x, int y)
{
    return x<y ? x : y;
}
void _(int&a , int b)
{
    a=(a%mod+b%mod)%mod;
    a=(a+mod)%mod;
}
ll cl(ll a,ll b)
{
    return (a/b)+(!(!(a%b)));
}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;cin >> n;
    cout << n+n*n+n*n*n;
    }

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

#define ll long long

int mod = 1e9 + 7;

ll power(ll x, ll n){
	ll result = 1;
	while(n){
		if (n&1)
			result = result*x%mod;
		n = n / 2;
		x = x * x % mod;
	}
	return result;
}


int main(){
	ll N; cin >> N;
	ll result = power(10, N);
	result -= power(9, N);
	result += mod;
	result %= mod;
	result -= power(9, N);
	result += mod;
	result %= mod;
	result += power(8, N);
	result %= mod;
	cout << result << "\n";
}

Measured memory_bytes: 3600
# https://atcoder.jp/contests/abc138/tasks/abc138_e

# s'は無限回繰り返されているとみなす
# sの中に含まれていない文字でtが構成されていたら速攻で-1

'''
1234567    ...                      33
contest contest contest contest contest contest
     s      e     nte     n     c   e

だけどcontestを無限に生成して、マッチングさせていくのでは最悪10**10になってTLEになってしまう。
貪欲を高速にやる必要あり。
つまりs`を回すんじゃなくて、tを回してできる方法を考える
t=sentenceなら 1文字目から次にsがでてくるのは5文字後、
6文字目から次にeが出てくるのは6文字後、
12文字目から...みたいに計算できる。 (12文字目は 12%7文字目に対応 (=0のときだけ7文字目に対応))

この操作に必要なのはsのi文字目(1-based-idx)において次に文字cが出てくるのは何文字後か、である。
'''

from collections import defaultdict
import sys
read = sys.stdin.readline

s = read()[:-1]
t = read()[:-1]
if set(t) - set(s):
    print(-1)
    exit()

# 前処理パート
S = s + s
# 逆向きから走査することでi文字目に置いて次にiが出てくるのはどこか見つける
tmp = {}  # いま文字keyが最後に出たのはいくつあとか
skiptable = [None] * (len(s) + 1)

# 前処理の前処理、
for i in range(len(S) - 1, -1, -1):
    moji = S[i]
    for key in tmp.keys():
        tmp[key] += 1  # すべて一文字あとになる
    if i < len(s):
        skiptable[i + 1] = tmp.copy()  # ミュータブルかつアドレス参照に注意
    tmp[moji] = 0  # その文字は0文字あとに修正


# 本処理
# 最初にうまく飛べる点を探索
for i, ss in enumerate(s):
    if ss == t[0]:
        now = i + 1
        break

for tt in t[1:]:
    idx = now % len(s)
    idx = idx if idx else len(s)
    now += skiptable[idx][tt]
print(now)


Measured memory_bytes: 225360
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using ll = long long;
using itn = int;
using namespace std;
int GCD(int a, int b){
    return b ? GCD(b, a%b) : a;
}
int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    int minCnt=1e9;
    for(int i=0; i<n; i++){
        int div=2;
        int cnt=0;
        while(!(a[i]%div)){
            div*=2;
            cnt++;
        }
        minCnt = min(minCnt, cnt);
    }
    cout << minCnt << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF (1e10)
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a * b / g;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}

int N, M;



int main()
{
	int H, W, N;
	cin >> H >> W >> N;
	int ans[H][W];
	int nowrow=0;
	int nowcol=0;
	REP(i, 1, N+1)
	{
		int a;
		cin >> a;
		REP(j,0,a){
			ans[nowrow][nowcol] = i;
			if(nowrow%2==0){
				if(nowcol==W-1){
					nowrow++;
				}else{
					nowcol++;
				}
			}else{
				if(nowcol==0){
					nowrow++;
				}else{
					nowcol--;
				}
			}
		}
	}

	REP(i,0,H){
		REP(j,0,W){
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}

	return 0;
}

Measured memory_bytes: 384
#include<stdio.h>
int Min(int,int);

int main(){
  int n,i,j,k,l;
  int f[101],s[101][101];
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%d %d",&f[i-1],&f[i]);
  }
  for(i=1;i<=n;i++){
    s[i][i]=0;
  }
  for(l=2; l<=n; l++){
    for(i=1; i<=n-l+1; i++){
      j=i+l-1;
      s[i][j]=1E+9;
      for(k=i; k<=j-1;k++){
    s[i][j] = Min(s[i][j],s[i][k]+s[k+1][j]+f[i-1]*f[k]*f[j]);
      }
    }
  }
    printf("%d\n",s[1][n]);
    return 0;
}

int Min(int a,int b){
  if(a<b){
    return a;
  }
  else{
    return b;
  }
}



Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

int d[3] = {-1, 0, 1};

ll f(ll a, ll b){
    ll res = LINF;
    rep(i, 3){
        rep(j, 3){
            ll p = (a * 2) / 3 + d[i];
            ll q = b / 2 + d[j];
            ll dif = max({p*q, p*(b-q), (a-p)*b}) - min({p*q, p*(b-q), (a-p)*b});
            res = min(dif, res);
        }
    }
    return res;
}



int main(){
    ll h, w;
    cin >> h >> w;

    if((h*w)%3 == 0) {
        cout << 0 << endl;
        return 0;
    }

    cout << min({h, w, f(h, w), f(w,h)}) << endl;

    return 0;
}


Measured memory_bytes: 256
# coding:utf-8

import sys
import itertools

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()

    dp = [[[[0] * 4 for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
    # 初期状態は直近3文字がTTTと見なせる
    dp[0][3][3][3] = 1

    A, C, G, T = 0, 1, 2, 3
    for i in range(n):
        for a, b, c, d in itertools.product(range(4), repeat=4):
            if b == A and c == G and d == C: continue
            if b == A and c == C and d == G: continue
            if b == G and c == A and d == C: continue
            if a == A and b == G and d == C: continue
            if a == A and c == G and d == C: continue
            dp[i + 1][b][c][d] = (dp[i + 1][b][c][d] + dp[i][a][b][c]) % MOD

    ans = 0
    for a, b, c in itertools.product(range(4), repeat=3):
        ans = (ans + dp[n][a][b][c]) % MOD

    return ans


print(main())


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

int main(){
  int h,a;
  cin >> h >> a;
  int ans=0;
  if(h%a>0){
    ans=h/a;
    ans++;
  }else{
    ans=h/a;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

constexpr long long maxw = 1e18;

using namespace std;

int n, sv, sw;
long long w[105];
int v[105];
long long dp[100003][105];

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

	for (int i = 1; i <= n; i++)
	{
		cin >> w[i] >> v[i];

		sv += v[i];
	}

	for (int i = 1; i <= sv; i++)
	{
		dp[i][0] = maxw;

		for (int j = 1; j <= n; j++)
		{
			long long res = maxw;

			if (i >= v[j])
				res = dp[i - v[j]][j - 1] + w[j];

			dp[i][j] = min(res, dp[i][j - 1]);
		}
	}

	for (int i = sv; i >= 1; i--)
	{
		if (dp[i][n] <= sw)
		{
			cout << i << endl;
			return 0;
		}
	}

	return 0;
}

Measured memory_bytes: 82304
#include<bits/stdc++.h>
#define range(i,a,b) for(long long i = (a); i < (b); i++)
#define rep(i,b) for(long long i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;
 
template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}
template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}


string del(string& s, int& ans){
	rep(i,s.size() - 2){
		if(s.substr(i, 3) == "(*)"){
			ans++;
			return s.substr(0, i) + '*' + s.substr(i + 3);
		}
	}
	rep(i,s.size() - 1){
		if(s.substr(i, 2) == "()"){
			return s.substr(0, i) + s.substr(i + 2);
		}
	}
	return s;
}


int main(){
	string s;
	while(cin >> s){
		s = '@' + s;
		int ans = 0;
		while(true){
			//show(s)
			string nxt = del(s, ans);
			if(s == nxt){
				break;
			}
			s = nxt;
		}
		cout << ans << endl;
	}
}



Measured memory_bytes: 3236
#include<stdio.h>
#include<stdlib.h>
int cmp(const int *a,const int *b){
  return *b-*a;
}
int main(){
  int n,a[334000],i;
  scanf("%d",&n);
  for(i=0;i<3*n;i++){
    scanf("%d",&a[i]);
  }
  qsort(a,3*n,4,cmp);
  long long ans;
  for(i=1;i<=n*2;i+=2){
    ans+=a[i];
  }
  printf("%lld",ans);
}

Measured memory_bytes: 2556
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> v(m);
    for (int i = 0; i < n; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int a;
            cin >> a;
            v[a-1]++;
        }
    }
    int ans = 0;
    for (int i = 0; i < m; ++i) {
        if(v[i] == n) ans++;
    }
    cout << ans << "\n";
    return 0;
}


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

int main() {
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i,N) cin >> A.at(i);
    //高いものに多くの割引券を使うべき
    //最初最大のものから割引券を使って行って、他に最大のものができたらそっちに使うということを繰り返す
    priority_queue<ll> q;
    rep(i,N) q.push(A.at(i));
    rep(i, M) {
        ll a = q.top()/2;
        q.pop();
        q.push(a);
    }
    ll ans = 0;
    while(!q.empty()) {
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 2168
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}
ll gcd(ll a, ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a, ll b){return a/gcd(a,b)*b;}



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

  ll a, b , x; cin >> a >> b >> x;
  ll l = a/x, r = b/x;
  if(a%x != 0) l++;
  cout << (r-l+1) << endl;
  
  
  //cout << fixed << setprecision(16) << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
double dp[3002][3002];
double a[3002];
bool vis[3002][3002];
double func(int n,int f)
{
	if((n==0&&f!=0)||(n>=1&&f<0))
		return 0;
	else if(n==0&&f==0)
		return 1;
	if(vis[n][f])
		return dp[n][f];
	dp[n][f]=func(n-1,f-1)*a[n]+func(n-1,f)*(1-a[n]);
	vis[n][f]=true;
	return dp[n][f];
}
int main()
{
	int n,i,j;
	double sum=0.0d;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=n;j++)
		{
			dp[i][j]=-1;
			vis[i][j]=false;
		}
	}
	for(i=n/2+1;i<=n;i++)
		sum+=func(n,i);
	cout<<fixed<<setprecision(12)<<sum<<endl;
}


Measured memory_bytes: 79616
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    int n;
    cin >> n;
    string s[n];
    rep(i, 0, n) {
        cin >> s[i];
    }

    if (n == 1) {
        vector<char> v;
        rep(i, 0, s[0].size()) {
            v.push_back(s[0][i]);
        }
        sort(v.begin(), v.end());
        rep(i, 0, v.size()) {
            cout << v[i];
        }
        cout << endl;
        return 0;
    }

    int common[26] = {};
    rep(i, 0, s[0].size()) {
        rep(j, 0, s[1].size()) {
            if (s[0][i] == s[1][j]) {
                common[s[0][i] - 'a']++;
                break;
            }
        }
    }


    rep(i, 2, n) {
        rep(j, 0, 26) {
            if (common[j]) {
                int cnt = 0;
                rep(k, 0, s[i].size()) {
                    if (s[i][k] == (char)(j + 'a')) {
                        cnt++;
                    }
                }
                common[j] = min(cnt, common[j]);
            }
        }
    }

    string ans;
    rep(i, 0, 26) {
        rep(j, 0, common[i]) {
            ans += (char)(i + 'a');
        }
    }

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


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

int n;
string s;
int layer;

int rec(string S, int depth){
	S = S.substr(1, S.length() - 2);
	if(S[0] != '['){
		int ret = 0;
		for(int i = 0; i < S.length(); i++){
			ret *= 10;
			ret += S[i] - '0';
		}
		return ret;
	}
	vector<int> va;
	int cnt = 0;
	int j = 0;
	for(int i = 0; i < S.length(); i++){
		if(cnt == 0) j = i;
		if(S[i] == '[') cnt++;
		if(S[i] == ']') cnt--;
		if(cnt == 0) va.push_back(rec(S.substr(j, i - j + 1), depth + 1));
	}
	sort(va.begin(), va.end());
	int ret = 0;
	for(int i = 0; i < va.size() / 2 + 1; i++){
		if(depth == layer - 2) ret += va[i] / 2 + 1;
		else ret += va[i];
	}
	return ret;
}

int main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s;
		layer = 0;
		int cnt = 0;
		for(int j = 0; j < s.length(); j++){
			if(s[j] == '[') cnt++;
			if(s[j] == ']') cnt--;
			layer = max(layer, cnt);
		}
		cout << rec(s, 0) << endl;
	}
	return 0;
}


Measured memory_bytes: 3192
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define fi first
#define se second
#define ep emplace
#define eb emplace_back
#define mp make_pair
#define pi pair<int,int>
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vll vector<ll>
#define vpll vector<pair<ll,ll>>
#define endl '\n'

#define si(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i) 
#define rep2(i, n, m) for (ll i = n; i <= (ll)(m); ++i)
#define rep3(i, n, m) for (ll i = n; i >= (ll)(m); --i)

template<class T, class U> bool chmax(T &a, U b) { if (a < b) a = b; return true; }
template<class T, class U> bool chmin(T &a, U b) { if (a > b) a = b; return true; }

using ll = long long;
using ld = long double;
using namespace std;

constexpr ll MOD = 1000000007;

signed main()
{
  cout << fixed << setprecision(20);
  ios::sync_with_stdio(false);
  cin.tie(0);

  ll n, d; cin >> n >> d;
  int ans = 0;

  rep(i, n) {
    ll x, y; cin >> x >> y;
    ll z = x*x + y*y;

    if (d*d >= z) ++ans;
  }

  cout << ans << endl;

  return (0);
}


Measured memory_bytes: 3652
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <deque>  
#include <iomanip>

using namespace std;

using ll = long long;
#define INF 1e9
#define MOD 1e9 + 7
#define rep(i, n) for(int i = 0; i < n; i++)
#define loop(i, a, n) for(int i = a; i < n; i++)
#define all(in) in.begin(), in.end()
int main(){
    char c[3][3];
    rep(i, 3)rep(k, 3) cin >> c[i][k];
    string ans = "";
    rep(i, 3)rep(k, 3){
        if(i == k) ans += c[i][k];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
# include <cstdio>
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
# define N 55
int a[N];
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	int sum=0;
	while(m>0){
		m--;
		sum+=a[n];
		n--;
	}
	printf("%d",sum);
	return 0;
}

Measured memory_bytes: 256
import java.io.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {

		long A = nextLong();
		long B = nextLong();
		long C = nextLong();
		long K = nextLong();
		long ans=0;

		ans+=Math.min(A, K);
		K-=Math.min(A, K);
		K-=Math.min(B, K);
		ans+=Math.min(C, K)*-1;

		System.out.println(ans);
	}
	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 25368
/**
 *    author:  math2do
 *    created: 05.05.2020 03:36:51 IST
**/

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0); 
  int n, x, y, z;
  cin >> n >> x >> y >> z;
  vector <string> arr(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  function <bool(int, int, int, int, vector <char>&)> recur = [&] (int i, int a, int b, int c, vector <char> &ans) {
    if (i == n) {
      cout << "Yes" << '\n';
      for (char ch : ans) {
        cout << ch << '\n';
      } 
      return true;
    } 
    if (arr[i] == "AB") {
      if (a > 0) {
        ans[i] = 'B';
        bool A = recur(i + 1, a - 1, b + 1, c, ans);
        if (A) return true;
      }
      if (b > 0) {
        ans[i] = 'A';
        bool B = recur(i + 1, a + 1, b - 1, c, ans);
        if (B) return true;
      }
    } 
    if (arr[i] == "AC") {
      if (a > 0) {
        ans[i] = 'C';
        bool A = recur(i + 1, a - 1, b, c + 1, ans);
        if (A) return true;
      } 
      if (c > 0) {
        ans[i] = 'A';
        bool B = recur(i + 1, a + 1, b, c - 1, ans);
        if (B) return true;
      }
    } 
    if (arr[i] == "BC") {
      if (b > 0) {
        ans[i] = 'C';
        bool A = recur(i + 1, a, b - 1, c + 1, ans);
        if (A) return true;
      }
      if (c > 0) {
        ans[i] = 'B';
        bool B = recur(i + 1, a, b + 1, c - 1, ans); 
        if (B) return true;      
      }
    } 
    return false;
  };
  vector <char> ans(n);
  bool found = recur(0, x, y, z, ans);
  if (!found) cout << "No" << '\n';
  return 0;
}


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

using namespace std;

int main(){
	int n,q;
	int S[10000];
	int T[500];
	int cnt = 0;

	fill_n(S,10000,0);
	fill_n(T,500,0);

	cin >> n;
	for(int i = 0;i < n;i++){
		cin >> S[i];
	}
	cin >> q;
	for(int i = 0;i <q;i++){
		cin >> T[i];
	}

	sort(S,S+n);

	for(int i = 0;i < q;i++){
		for( int j = 0;j < n;j++){
			if(T[i] < S[j])break;
			if(T[i] == S[j]){
				cnt++;
				break;
			}
		}
	}
	cout << cnt << endl;
}

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

#define int long long
#define INT int
#define MOD 1000000007

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
template <typename T>
void print(T x)
{
    std::cout << x << '\n';
}
typedef long long ll;
const long long INF = 1LL << 60;

template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

// DPテーブル
int dp[3100][3100] = {0}; // 初期値も初期条件も 0

signed main()
{
    string s, t;
    cin >> s >> t;

    rep(i, s.size())
    {
        rep(j, t.size())
        {
            if (s[i] == t[j])
            {
                chmax(dp[i + 1][j + 1], dp[i][j] + 1);
            }
            chmax(dp[i + 1][j + 1], dp[i + 1][j]);
            chmax(dp[i + 1][j + 1], dp[i][j + 1]);
        }
    }
    string res = "";

    int i = (int)s.size();
    int j = (int)t.size();

    while (i > 0 && j > 0)
    {
        if (dp[i][j] == dp[i - 1][j])
        {
            i--;
        }
        else if (dp[i][j] == dp[i][j - 1])
        {
            j--;
        }
        else
        {
            res = s[i - 1] + res;
            i--;
            j--;
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 76312
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    int t=1;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.size();
        map<int,int>cnt;
        for(int i=0; i<n; i++)
        {
            cnt[s[i]-'a']++;
        }
        bool flag=true;
        for(int i=0; i<26; i++)
        {
            if(cnt[i]%2==1)
            {
                flag=false;
                break;
            }
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
        cnt.clear();
    }
}


Measured memory_bytes: 3612
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PI  3.14159265358979323846
#define M   1000000007
ll gcd(ll a,ll b)
{
    if(a==0)
        return b;
    else
        return gcd(b%a,a);
}
ll fast(ll n,ll a,ll m)
{
    if(n==0)
        return 1;
    else if(n==1)
        return a;
    else
    {
        ll res=fast(n/2,a,m)%m;
        if(n%2==0)
            return (((res%m)*(res%m))%m);
        else
            return (((((res%m)*a)%m)*res)%m);
    }
}
ll lcm(ll a,ll b)
{
    ll p=a*b;
    p/=gcd(a,b);
    return p;
}
ll isprime(ll N)
{
    if(N==2||N==3)
    {
        return 1;
    }
    if(N%2==0||N%3==0)
    {
        return 0;
    }
    for(ll i=5;i*i<=N;i+=6)
    {
        if(N%i==0||N%(i+6)==0)
            return 0;
    }
    return 1;
}

int main()
{
  ll n,i,H;
  cin>>H>>n;
  ll A[n];
  ll S=0;
  for(i=0;i<n;i++)
  {
      cin>>A[i];
      S+=A[i];
  }
  if(S>=H)
    cout<<"Yes";
  else
    cout<<"No";

}


Measured memory_bytes: 1024
#include <cstdio>
#include <algorithm>
using namespace std;

int v[1001],w[1001],dp[10001][10001];
int N,W;

int main(){
    scanf("%d%d",&N,&W);
    for(int i = 0;i <N;i++)
        scanf("%d%d",&v[i],&w[i]);
    for(int i = 1;i <= N;i++)
        for(int j = 0;j <= W;j++){
            if(j - w[i-1] < 0)
                dp[i][j] = dp[i-1][j];
            else
                dp[i][j] = max(dp[i-1][j],dp[i][j-w[i-1]] + v[i-1]);
        }
    printf("%d\n",dp[N][W]);

    return 0;
}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

int main()
{
    lint n;cin >> n;
    string ans = "";
    //char tmp2 = (char)((n % 26) + 'a' - 1);
    //ans = ans + tmp2;
    while(n>0){
        lint x = n / 26ll;
        lint a = n % 26ll + (lint)'a' - 1ll;

        //cout << n % 26ll << "\n";
        char tmp = (char)(a);
        if (n % 26ll==0){
            ans += 'z';
        }else{
            ans = ans + tmp;
        }
        int zzz = 0;
        if (n % 26ll==0){
            zzz = 1;
        }
            n = n / 26ll -  zzz;
    }
    reverse(ALL(ans));
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <map>
using namespace std;
typedef unsigned long long UL;

int main(int argc, char* argv[])
{
	UL N;
	cin>>N;
	UL A;
	UL i;
	map<UL,int> aMap;
	map<UL,int>::iterator mit;
	map<UL,int> bMap;
	for (i=0;i<N;i++){
		cin>>A;
		mit=aMap.find(A);
		if (mit!=aMap.end()){
			(*mit).second++;
		}else{
			aMap[A]=1;
		}
	}
	for (mit=aMap.begin();mit!=aMap.end();mit++){
		if ((*mit).second>=2){
			bMap[(*mit).first]=(*mit).second;
		}
	}
	aMap.clear();
	if (bMap.size()<2){
		cout<<0<<endl;
		return 0;
	}
	UL area=1;
	int num=0;
	map<UL,int>::reverse_iterator mit1;
	for (mit1=bMap.rbegin();mit1!=bMap.rend();mit1++){
		if (num==0){
			if ((*mit1).second>=4){
				cout<<(*mit1).first * (*mit1).first<<endl;
				return 0;
			}
		}
		area*=(*mit1).first;
		num++;
		if (num==2){
			cout<<area<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 6528
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <utility>
#include <algorithm>
#include <sstream>
using namespace std;

struct Node{
	int x,y;
};

const int max_n=1000+10;
int h,w,n,dx[]={0,0,-1,1},dy[]={-1,1,0,0},d[max_n][max_n],ans;
Node sN;
char c[max_n][max_n];

void bfs(int m){
	if(m>n)return;
	queue<Node> q;
	memset(d,0,sizeof(d));
	q.push(sN);
	d[sN.x][sN.y]=1;
	while(!q.empty()){
		Node p=q.front();
		q.pop();
		
		if(c[p.x][p.y]=='0'+m){
		    ans+=d[p.x][p.y]-1;
		    sN.x=p.x;
		    sN.y=p.y;
		    return;
		}
		for(int i=0;i<4;i++){
			Node nN;
			nN.x=p.x+dx[i];
			nN.y=p.y+dy[i];
			if(nN.x>=0 && nN.x<h 
            && nN.y>=0 && nN.y<w 
		   	&& c[nN.x][nN.y]!='X' && !d[nN.x][nN.y]){
				q.push(nN);
				d[nN.x][nN.y]=d[p.x][p.y]+1;
			}
		}
	}
}

int main(){
    scanf("%d%d%d",&h,&w,&n);
    for(int i=0;i<h;i++)
        scanf("%s",c[i]);
    for(int i=0;i<h;i++)
        for(int j=0;j<w;j++)
            if(c[i][j]=='S'){
            	sN.x=i;
            	sN.y=j;
            	break;
            }
    for(int i=1;i<=n;i++)bfs(i);
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 8164
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  int l = m;
  if(l==0)l=1;
    vector<int> a(l);
  int i;
  for(i=0;i<m;i++){
    cin >> a[i];
  }
 
  long ans;
  vector<long> b(n+1);
  b[0] = 1;
  if(a[0] == 1){
    b[1] = 0;
  }else{b[1] = 1;}
    int j =0;
  while(j != m && a[j] == 1)j++;
  for(i=2;i<n+1;i++){
    while(j != m && a[j] == a[j+1])j++;
    if(i ==a[j]){
      b[i] = 0;
      if(j!=m)
        j++;
    }else{
      b[i] = b[i-1] + b[i-2];
    }
    if(b[i] > 1000000007)b[i] %= 1000000007;
  }
  cout << b[n] << endl;
}

Measured memory_bytes: 1408
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int top, S[1000];

void push(int x) {
    S[++top] = x;
}

int pop() {
    top--;
    return S[top+1];
}

int main() {
    int a,b;
    top = 0;
    char s[100];
    while( scanf("%s", s) != EOF ) {
        if ( s[0] == '+') {
            a = pop();
            b = pop();
            push(a+b);
        } else if ( s[0] == '-') {
            b = pop();
            a = pop();
            push(a-b);
        } else if ( s[0] == '*') {
            a= pop();
            b = pop();
            push(a * b);
        } else {
            push(atoi(s));
        }
    }

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

    return 0;

}



Measured memory_bytes: 2104
N, x = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

ans = 0
if a[0] > x
	ans += a[0] - x
	a[0] = x
end
(N-1).times do |i|
	tmp = a[i] + a[i+1] - x
	if tmp > 0
		a[i+1] -= tmp
		ans += tmp
	end
end
print ans, "\n"


Measured memory_bytes: 8580
x=int(input())
if x>=1800:
    print(1)
elif x>=1600:
    print(2)
elif x>=1400:
    print(3)
elif x>=1200:
    print(4)
elif x>=1000:
    print(5)
elif x>=800:
    print(6)
elif x>=600:
    print(7)
elif x>=400 :
    print(8)

Measured memory_bytes: 9180
c = []
c.append(list(map(int, input().split())))
c.append(list(map(int, input().split())))
c.append(list(map(int, input().split())))

for i in range(2):
    # vertical
    dif0 = c[0][i + 1] - c[0][i]
    dif1 = c[1][i + 1] - c[1][i]
    dif2 = c[2][i + 1] - c[2][i]
    if dif0 == dif1 and dif1 == dif2:
        continue
    else:
        print("No")
        exit()

    # horizon
    dif0 = c[i + 1][0] - c[i][0]
    dif1 = c[i + 1][1] - c[i][1]
    dif2 = c[i + 1][2] - c[i][2]
    if dif0 == dif1 and dif1 == dif2:
        continue
    else:
        print("No")
        exit()

print("Yes")

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
signed main(){
  Int T,D,L;
  while(cin>>T>>D>>L,T||D||L){
    Int x[T];
    for(Int i=0;i<T;i++) cin>>x[i];
    Int ans=0,cnt=0;
    for(Int i=0;i<T-1;i++){
      if(cnt) cnt--;
      if(L<=x[i]) cnt=D;
      if(cnt) ans++;
    }
    cout<<ans<<endl;
  }
  return 0;
}



Measured memory_bytes: 3872
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
	int n, m; scanf("%d%d", &n, &m);
	std::vector<int> h(n, 0);
	std::vector<std::vector<int>> g(n);
	for(int i = 0; i < m; i++) {
		int a, b; scanf("%d%d", &a, &b);
		
		g[a - 1].push_back(b - 1);
		h[b - 1]++;
	}
	
	std::queue<int> qu;
	std::vector<int> dp(n, 0);
	for(int i = 0; i < n; i++) if(!h[i]) qu.push(i);
	while(!qu.empty()) {
		auto p = qu.front(); qu.pop();
		
		for(auto e: g[p]) {
			dp[e] = std::max(dp[e], dp[p] + 1);

			if(!(--h[e])) qu.push(e);
		}
	}
	
	int ans = 0;
	for(auto v: dp) ans = std::max(ans, v);
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 6528
def solve():
    n = int(input())
    A = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    R = A[n:] + A[:n]
    M = {A[i]: R[i] for i in range(26)}
    ans = ""
    for s in input():
        ans += M[s]
    print(ans)
solve()


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

vector<int> ch(100005);

int main() {
    ll N, X, M; cin >> N >> X >> M;

    if(X == 0){
        cout << 0 << endl;
        return 0;
    } else if(X == 1){
        cout << N << endl;
        return 0;
    }

    vector<ll> A;
    A.push_back(X);
    ch[X]++;
    ll st = 0;
    while(1){
        X *= X;
        X %= M;
        if(X == 0){
            A.push_back(0);
            break;
        } else if(X == 1) {
            A.push_back(1);
            break;
        }
        if(ch[X] == 0){
            ch[X]++;
            A.push_back(X);
        } else {
            st = X;
            break;
        }
    }

    ll n = A.size();
    ll total = 0;
    if(n > N){
        for (int i = 0; i < N; i++){
            total += A[i];
        }
        cout << total << endl;
        return 0;
    }

    rep(i, n){
        total += A[i];
    }

    if(A[n-1] == 0){
        cout << total << endl;
    } else if(A[n-1] == 1){
        cout << total + (N - n) << endl; 
    } else {
        ll f;
        rep(i, n){
            if(A[i] == st){
                f = i;
                break;
            }
        }
        ll total2 = 0;
        for (int i = f; i < n; i++){
            total2 += A[i];
        }
        ll k = n - f;
        ll nokori = N - n;
        ll roop = nokori / k;
        ll saigo = nokori % k;
        ll total3 = 0;
        for (int i = f; i < f+saigo; i++){
            total3 += A[i];
        }

        cout << total + total2*roop + total3 << endl;

    }


    return 0;
}

Measured memory_bytes: 4196
#include<string>
#include<iostream>
int n,k;
std::string s[4][7]={{"aacd","bbcd","cdaa","cdbb"},{"aa.ab",".bbab","a.cca","a.a.a","bbabb"},{"aacd..","bbcd..","cd..aa","cd..bb","..aacd","..bbcd"},{"aacd...","bbcd...","cd.aa..","cd...bb","..a.baa","..a.b.b","..bbaab"}};
int main()
{
    std::cin>>n,k=n&3;
    if(n<3) std::cout<<"-1\n";
    else if(n==3) std::cout<<"aab\nb.b\nbaa\n";
    else for(int i=0;i<n;++i)
     {
         std::string t(n,'.');
         i<n-k-4? t.replace(i/4*4,4,s[0][i%4]):t.replace(n-k-4,k+4,s[k][i-n+k+4]);
         std::cout<<t<<'\n';
     }
}

Measured memory_bytes: 1280
N, M, C = map(int, input().split())
B = list(map(int, input().split()))

count = 0
for i in range(N):
    lst = list(map(int, input().split()))
    lb = 0
    for l,b in zip(lst,B):
        lb += l * b
    if lb + C > 0:
        count += 1

print(count)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define pt(sth) cout << sth << "\n"
#define chmax(a, b) {if(a<b) a=b;}
#define chmin(a, b) {if(a>b) a=b;}
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
static const ll INF=1e18;
static const ll MAX=101010;
static const ll MOD=1e9+7;




int main(void) {
  ll N, K;
  cin >> N >> K;
  P su[MAX];
  ll i;
  
  for(i=0; i<N; i++) {
    cin >> su[i].second >> su[i].first;
    su[i].second--;
  }
  sort(su, su+N);
  reverse(su, su+N);
  
  ll ans=0;
  ll clr=0;
  ll cnt[MAX]={};
  for(i=0; i<K; i++) {
    cnt[su[i].second]++;
    ans+=su[i].first;
    
    if(cnt[su[i].second]==1) clr++;
  }
  ans+=clr*clr;
  
  ll t=ans-clr*clr;
  ll k=K-1;
  
  for(i=K; i<N; i++) {
    
    if(cnt[su[i].second]) continue;
    
    while(k>=0 && cnt[su[k].second]==1) k--;
    
    if(k<0) break;
    
    cnt[su[k].second]--;
    t-=su[k].first;
    k--;
    
    cnt[su[i].second]++;
    t+=su[i].first;
    clr++;
    
    chmax(ans, t+clr*clr);
  }
  
  pt(ans);
  
}




Measured memory_bytes: 2560
#N = int(input())
X,K,D= list(map(int,input().split()))
cnt = 0
if X <= 0:
    X *=-1

if X/K >= D:
    print(X-K*D)
    exit()

while X >= 0 :
    X -= D
    cnt += 1

if ((K-cnt) % 2 == 0):
    print(X*-1)
else :
    print(X+D)

Measured memory_bytes: 62652
from collections import deque

n = int(input())
node_data = [[] for i in range(n+1)]
node_stuck = deque([])
Fennec = [0] * (n+1)
Snuke = [0] * (n+1)
for i in range(n-1):
    x, y = list(map(int, input().split()))
    node_data[x].append(y)
    node_data[y].append(x)
node_stuck.append([1,0])
finished = set()

while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Fennec[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count+1])
node_stuck.append([n,0])
finished = set()
while  len(node_stuck) > 0:
    data = node_stuck.pop()
    index = data[0]
    count = data[1]
    finished.add(index)
    Snuke[index] = count
    for i in node_data[index]:
        if i not in finished:
            node_stuck.append([i,count + 1]) 
f = 0
s = 0
##print("Fennec => {}".format(Fennec))
##print("Snuke  => {}".format(Snuke))
for i in range(2, n):
    if Fennec[i] <= Snuke[i]:
        f += 1
    else:
        s += 1

if f > s:
    print("Fennec")
else:
    print("Snuke")
    






Measured memory_bytes: 42432
#include<bits/stdc++.h>
using namespace std;
long long dp[3005][6005]={0};
int a[3005];
const long long MOD=998244353;
int main()
{
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=s;i++)
        dp[0][i]=0;
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=i+1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=s;j++)
        {
            if(j>=a[i])dp[i][j]=(dp[i-1][j]+dp[i-1][j-a[i]])%MOD;
            else dp[i][j]=dp[i-1][j];
        }
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
        ans=(ans+dp[i][s])%MOD;
    cout<<ans<<'\n';
}


Measured memory_bytes: 139520
#include <cstdio>
#include <algorithm>
using namespace std;
long long mp(long long b, long long e, long long m) {
	if (e == 0) return 1;
	long long a = mp(b, e / 2, m);
	a = a * a % m;
	if (e & 1) a = a * b % m;
	return a;
}
int get_ans(int X) {
	if (X == 0) return 0;
	return get_ans(X % __builtin_popcount(X)) + 1;
}
int main() {
	int N, pc = 0;
	scanf("%d", &N);
	char X[N];
	for (int i = 0; i < N; ++i) scanf(" %c", &X[i]);
	for (int i = 0; i < N; ++i) {
		if (X[i] == '1') ++pc;
	}
	int tz = 0, to = 0;
	for (int i = 0; i < N; ++i) {
		if (pc > 1) tz = ((tz << 1) + (X[i] == '1')) % (pc - 1);
		to = ((to << 1) + (X[i] == '1')) % (pc + 1);
	}
	for (int i = 0; i < N; ++i) {
		if (X[i] == '0') printf("%d\n", get_ans((to + mp(2, N - 1 - i, pc + 1)) % (pc + 1)) + 1);
		else if (pc == 1) printf("0\n");
		else printf("%d\n", get_ans((tz - mp(2, N - 1 - i, pc - 1) + pc - 1) % (pc - 1)) + 1);
	}
	return 0;
}

Measured memory_bytes: 2020
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = b-1; i >= a; i--)
// #define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

////////////////////////////////////////////////////////

int main() {
    ll k; cin >> k;
    ll a = 7;
    rep(i, 1, k+1){
        if(a%k == 0){
            co(i);
            return 0;
        }
        a %= k;
        a = a*10 + 7;
    }
    co(-1);
    
    return 0;
}




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

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<pdd> vdd;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define mem(a,b) memset(a, b, sizeof(a) )
#define all(x) (x).begin(),(x).end()
#define INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int n,m;cin>>n>>m;
    vi h(n);
    rep(i,n)cin>>h[i];
    vvi g(n);
    rep(i,m){
        int a,b;
        cin>>a>>b;
        a--;b--;
        g[a].PB(b);
        g[b].PB(a);
    }
    int ans=0;
    rep(i,n){
        bool a=true;
        for(int j=0;j<g[i].size();++j){
            if(h[i]<=h[g[i][j]]){
                a=false;
                break;
            }
        }
        if(a){ans++;}
        
    }
    cout<<ans<<endl;
}


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

int largestRectangleArea(vector<int>& heights)
{
    int n = heights.size() ;
    int a[n+2] , l[n+1] , r[n+1] , ans = 0 ;
    stack<int> s , p ;
    for(int i = 1 ; i <= n ; ++i) a[i] = heights[i-1] ;
    a[0] = -1 , a[n+1] = -1 ;
    s.push(0) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        while(a[s.top()]>=a[i]) s.pop() ;
        l[i] = s.top() ;
        s.push(i) ;
    }
    p.push(n+1) ;
    for(int i = n ; i > 0 ; --i)
    {
        while(a[p.top()]>=a[i]) p.pop() ;
        r[i] = p.top() ;
        p.push(i) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        ans = max(ans,(a[i]+1)*(r[i]-l[i])) ;
    }
    return ans ;
}

int main()
{
    int h , w ;
    scanf("%d%d",&h,&w) ;
    string s ;
    int grid[h][w] , grid2[h][w] , ans = max(h,w) ;
    memset(grid2,0,sizeof(grid2)) ;
    for(int i = 0 ; i < h ; ++i)
    {
        cin>>s ;
        for(int j = 0 ; j < w ; ++j)
        {
            if(s[j]=='.') grid[i][j] = 0 ;
            else grid[i][j] = 1 ;
        }
    }
    for(int i = 0 ; i < h - 1 ; ++i)
    {
        for(int j = 0 ; j < w - 1 ; ++j)
        {
            if((grid[i][j]+grid[i+1][j]+grid[i][j+1]+grid[i+1][j+1])%2==0) grid2[i][j] = 1 ;
            else grid2[i][j] = 0 ;
        }
    }
    --h , --w ;
    vector<int> v ;
    for(int i = 0 ; i < h ; ++i)
    {
        for(int j = 0 ; j < w ; ++j)
        {
            if(!i) v.push_back(grid2[i][j]) ;
            else
            {
                if(grid2[i][j]==0) v[j] = 0 ;
                else ++v[j] ;
            }
        }
        ans = max(ans,largestRectangleArea(v)) ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}


Measured memory_bytes: 31616
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int count =0;
		int A[] = new int[200000];
		for (int i=0;i<N;i++) {
			int temp = sc.nextInt();
			if (temp>N) {
				count ++;
			} else {
				A[temp]++;
			}
		}
		for (int i=0;i<A.length;i++) {
			if (A[i]>i) {
				count +=A[i]-i;
			} else if (A[i]<i) {
				count +=A[i];
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 61884
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define ll long long
#define pp pair<int,int> 
//int 2×10の9乗
 
int main() {
  int a, b, k;
  cin >> a >> b >> k;
  //int m = min(a,b);
  for (int i = min(a,b); i >= 1; i--){
    if(a%i==0 && b%i==0) {
      k--;
     if(k==0) {cout << i << endl;
     return 0;
     }
    }
  }
}

Measured memory_bytes: 256