akhauriyash/Code-Regression huggingface dataset:
// Try AtCoder
// author: Leonarone @ NEETSDKASU
package main

import "fmt"

func main() {
    var o, e string
    fmt.Scan(&o, &e)
    for len(o) > 0 || len(e) > 0 {
        fmt.Print(o[0:1])
        o = o[1:]
        if len(e) > 0 {
            fmt.Print(e[0:1])
            e = e[1:]
        }
    }
    fmt.Println()
}

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

int main() {
  int n,k;
  cin >> n >> k;
  int m = n-1;
  int cnt = (n-2)*(n-1)/2;
  if(cnt < k){
    cout << -1 << endl;
    return 0;
  }
  vector<vector<bool>>data(n,vector<bool>(n,false));
  rep(i,1,n){
    data[0][i] = true;
    data[i][0] = true;
  }
  rep(i,1,n){
    if(cnt == k) break;
    rep(j,1,n){
      if(cnt == k) break;
      if(i == j) continue;
      if(!data[i][j]){
        cnt--;
        m++;
        data[i][j] = true;
        data[j][i] = true;
      }
    }
  }
  cout << m << endl;
  rep(i,0,n){
    rep(j,0,i){
      if(data[i][j]) cout << i+1 << " " << j+1 << endl;
    }
  }
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
using ll=long long;
constexpr ll mod=1000000007;
constexpr int inf=1000000000;
constexpr ll linf=1000000000000000000;

int main(){
    int n;
    string s;
    cin>>n>>s;
    int r[n+1],g[n+1],b[n+1]={};
    rep(i,n){
        r[i+1]=r[i]+(s[i]=='R');
    }
    rep(i,n){
        g[i+1]=g[i]+(s[i]=='G');
    }
    rep(i,n){
        b[i+1]=b[i]+(s[i]=='B');
    }
    ll ans=0;
    rep(i,n){
        for(int j=i+1;j<n;++j){
            if(s[i]==s[j])continue;
            int d=j-i;
            if(s[i]!='R'&&s[j]!='R'){
                ans+=r[n]-r[j+1];
                if(j+d<n&&s[j+d]=='R')--ans;
            }
            if(s[i]!='G'&&s[j]!='G'){
                ans+=g[n]-g[j+1];
                if(j+d<n&&s[j+d]=='G')--ans;
            }if(s[i]!='B'&&s[j]!='B'){
                ans+=b[n]-b[j+1];
                if(j+d<n&&s[j+d]=='B')--ans;
            }
        }
    }
    cout<<ans<<endl;
}


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

using namespace std;

const int MAX = 100001;
int n, arr[MAX], dp[MAX];

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n;
  
  memset(dp, 0x3f, sizeof(dp));
  dp[0] = 0;
  
  for(int i=0;i<n;i++)cin>>arr[i];
  for(int i=0;i<n-1;i++){
    dp[i+1]=min(dp[i+1],dp[i]+abs(arr[i+1]-arr[i]));
    if(i<n-2)dp[i+2]=min(dp[i+2],dp[i]+abs(arr[i+2]-arr[i]));
  }
  cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/
 
const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

ll modpow(ll x, ll n){
    if(n == 0) return 1;

    ll res = modpow(x, n/2);
    if(n%2 == 0) return res*res%mod;
    else return res*res%mod*x%mod;
}

ll power(ll x, ll n){
    if(n == 0) return 1;

    ll res = power(x, n/2);
    if(n%2 == 0) return res*res;
    else return res*res*x;
}

int getl(int i, int N) { return i==0? N-1:i-1; };
int getr(int i, int N) { return i==N-1? 0:i+1; };

/* <--------------------------------------------> */

typedef tuple<ll, ll, ll> T;
// get<K>(tuple型の変数)


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

    ll inf = 1LL<<60;
    int n; cin >> n;
    vector<ll> h(n+5, inf);
    for(int i=0; i<n; ++i) cin >> h[i];

    int ans = 0;
    int r=0;
    for(int i=0; i<n; ++i){
        chmax(r, i);
        while(r+1<n && h[r+1] <= h[r]) ++r;
        chmax(ans, r-i);
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
    int n;
    int count=0;
    cin>>n;
    char ar[100000];
    for(int i=0; i<n; i++)
    {
        cin>>ar[i];
    }
    for(int i=0; i<n; i++)
    {
        if(ar[i]==ar[i+1])
        {
            continue;
        }
        count++;
    }
    cout<<count;
}


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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

int dp[105][10005];

int main()
{
    rep(i, 105) rep(j, 10005) dp[i][j] = 0;
    int n, w;
    cin >> n >> w;
    int value[n], wight[n];
    rep(i, n) cin >> value[i] >> wight[i];

    rep(i, n)
    {
        rep(j, 10005)
        {
            if (j - wight[i] >= 0)
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - wight[i]] + value[i]);
            else
                dp[i + 1][j] = dp[i][j];
        }
    }

    OP(dp[n][w]);

    return 0;
}


Measured memory_bytes: 7220
import java.util.Scanner;


	public class Main {
		
		
		public static int n;
		public static int m;
		public static int[] k;
		public static int[][] s;
		public static int[] p;
		public static int ret;
		public static int ret2;
		public static int[] sw;
		
		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			n = sc.nextInt();
			m = sc.nextInt();
			k = new int[m];
			s = new int[m][n];
			p = new int[m];
			sw = new int[n];
			ret = 0;
			
			
			
			
			for(int i=0;i<m;i++) {
				k[i] = sc.nextInt();
				
				for(int j=0;j<k[i];j++) {
					s[i][j] = sc.nextInt();
				}
			}
			
			for(int i=0;i<m;i++) {
				p[i] = sc.nextInt();
			}
			
			dfs(0);
			
			System.out.println(ret);
			
	    }
		
		public static void dfs(int index) {
			
			if(index==n) {
				
				ret2 =0;
				for(int i=0;i<m;i++) {
					int sum = 0;
					for(int j=0;j<k[i];j++) {
						sum+=sw[(s[i][j]-1)];
					}
					
					if(sum%2!=p[i]) {
						return;
					}
					
				}
				ret++;
				
				
				return;
			}
			
			sw[index] = 0;
			dfs(index+1);
			
			sw[index] = 1;
			dfs(index+1);
			
		}
		
	}
	


Measured memory_bytes: 37528
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main(){

    input!{
        a: i64,
        b: i64,
        k: i64,
    }

    let cockey = a + b - k;
    if cockey <= 0 {
        println!("0 0");
    } else if cockey <= b {
        println!("0 {}", cockey);
    } else if cockey > b{
        println!("{} {}", a - k, b);
    }

}

Measured memory_bytes: 4352
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

ll a[225816];

int main(void){
	int n,i;
	ll k,ans=-INFLL;
	cin >> k >> n;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	a[n] = a[0]+k;
	for(i=0; i<n; ++i){
		ans = max(ans,a[i+1]-a[i]);
	}
	cout << (k-ans) << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <string>

using namespace std;

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

    int max_price = 0;
    int total_price = 0;

    for(int i = 0; i < n; i++)
    {
        int p;
        cin >> p;
        if (p > max_price)
        {
            max_price = p;
        }
        total_price += p;
    }

    total_price -= max_price / 2;

    cout << total_price;

    return 0;
}

Measured memory_bytes: 256
import sys

alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

ina = input()

place = alphabet.index(ina)

nn = int(place) + 1

print(alphabet[nn])

Measured memory_bytes: 3060
#include <iostream>
#include <stdio.h>
#include <vector> 
#include <math.h> 
#include <regex>
typedef long long ll;
using namespace std;

void saiki(ll S, ll &count, int use, ll N) {
    if (S > N) return;
    if (use == 0b111) count++;

    saiki(S * 10 + 3, count, use | 0b001, N);
    saiki(S * 10 + 5, count, use | 0b010, N);
    saiki(S * 10 + 7, count, use | 0b100, N);
}
int main(void){
    ll N; cin >> N;
    ll count = 0;
    saiki(0,count,0,N);
    cout << count << endl;
}


Measured memory_bytes: 3608
object Main {
  def main(args:Array[String]) = {
    val arr =  readLine.split(" ").map(_ .toInt)
    val out = readLine.split("").takeRight(arr(0))
    for (x <-0 until arr(0)){
      if (( x+1) == arr(1) ){
      	print(out(x)toLowerCase)
      }else{
        print(out(x))
      }  
    }
  }
}

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

const int MAX = 200000;
int main() {
	int N, M, a, b;
	static int x[MAX];
	cin >> N >> M;
	for (int i = 0;i < N;i ++) x[i] = 0;
	for (int i = 0;i < M;i ++) {
		cin >> a >> b;
		if (a == 1) {
			x[b - 1] ++;
			if (x[b - 1] >= 2) {
				cout << "POSSIBLE";
				return 0;
			}
		} else if (b == N) {
			x[a - 1] ++;
			if (x[a - 1] >= 2) {
				cout << "POSSIBLE";
				return 0;
			}
		}
	}
	cout << "IMPOSSIBLE";
	return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1e5+4;
const int mod=1e9+7;
vector<int> adj[N];
vector<int> vis(N,0);
void dfs(int x){
    if(vis[x]){
        return;
    }
    vis[x]=1;
    for(auto i:adj[x]){
        dfs(i);
    }
}
void solve(){
    int n,m; cin>>n>>m;
    int ss=m;
    while(ss--){
        int u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            cnt++;
            dfs(i);
        }
    }
    cout<<cnt-1<<endl;
}   
int32_t main(){
    // ios_base::sync_with_stdio(false);cin.tie(NULL);
    int tt; 
    tt=1;
    // cin>>tt;
    for(int t=1;t<=tt;t++){
        solve();
    }
} 

Measured memory_bytes: 10588
#include <stdio.h>
#include <assert.h>

int main(int argc, char* argv[]) {
    int n, i;
    int ret;
    int min = 0;
    int max_profit;
    int r;

    ret = scanf("%d\n", &n);
    assert( ret == 1 );
    assert( (2 <= n) && (n <= 200000) );

      /* first value */
    ret = scanf("%d\n", &min);
    assert( ret == 1 );

      /* 2nd value */
    ret = scanf("%d\n", &r);
    assert( ret == 1 );
    max_profit = r - min;

    if ( r < min ) {
        min = r;
    }
    
    for ( i = 2; i < n; i++ ) {
        int p;
        ret = scanf("%d\n", &r);
        assert( ret == 1 );
        assert( (1 <= r) && (r <= 1000000000) );

        p = r - min;
        if ( p > max_profit ) {
            max_profit = p;
        }
        if ( r < min ) {
            min = r;
        }
    }
        
    printf("%d\n", max_profit);

    return 0;
}



Measured memory_bytes: 2120
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
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;
}
int main(){
    ll n;cin >>n;
    vl a(n),b(n),c(n);
    rep(i,n)cin >> a[i];
    rep(i,n)cin >> b[i];
    rep(i,n)cin >> c[i];
    sort(all(a));
    sort(all(b));
    sort(all(c));
    vl ccnt(n),bsum(n);
    rep(i,n){
        auto iter=upper_bound(all(c),b[i]);
        ccnt[i]=c.end()-iter;
    }
    ll count=0;
    per(i,n){
        count+=ccnt[i];
        bsum[i]=count;
    }
    ll ans=0;
    rep(i,n){
        auto iter=upper_bound(all(b),a[i]);
        ans+=bsum[iter-b.begin()];
    }
    cout <<ans <<endl;
}

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

typedef long double ld;

const ld eps = 1.0e-11; // 許容される誤差

ld mysqrtl(ld x)
{
  ld a = sqrt((double)x); // 近似値
  do {
    a = (a + x/a) / 2.0L;
  } while (fabsl(x - a*a) > eps);
  return a;
}

int main (void)
{
    long double a, b, h, m, c;
    double theta, h_theta, m_theta;

    scanf("%Lf %Lf %Lf %Lf", &a, &b, &h, &m);

    h_theta = 360 * ((60 * h + m) / (60 * 12));
    m_theta = 360 * (m / 60);
    theta = M_PI*fabs(h_theta - m_theta)/180;

    c = pow(a, 2.0) + pow(b, 2.0) - (2 * b * a * cos(theta));

    if (theta == 0) {
        printf("%lf", fabs((double)a-(double)b));
    } else {
        printf("%.15Lf", mysqrtl(c));
    }

    return 0;
}


Measured memory_bytes: 2612
N = int(input())
a = list(map(int, input().split()))
avg = round(sum(a)/N)
sums = []
for i in range(min(a), avg+1):
    s = 0
    for j in range(N):
        s += (i-a[j])**2
    sums.append(s)
print(min(sums))

Measured memory_bytes: 9004
from collections import deque
N,M = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
col = [-1 for _ in range(N+1)]
cnt = 0
for i in range(1,N+1):
    if col[i]<0:
        col[i]=cnt
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if col[y]<0:
                    col[y] = cnt
                    que.append(y)
        cnt += 1
C = {}
for i in range(1,N+1):
    a = col[i]
    if a not in C:
        C[a] = 0
    C[a] += 1
cmax = 0
for a in C:
    cmax = max(cmax,C[a])
print(cmax)

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

using Edge=pair<int,int>;
using Graph=vector<vector<Edge>>;

vector<int> color;

//親pを持つvを塗るdfs
void paint(Graph &T,int v,int p){

  for(auto nv:T[v]){
    if(nv.first==p){
      if(nv.second%2==0){
        color[v]=color[p];
      }
      else{
        color[v]=1-color[p];
      }
    }
  }

  for(auto nv:T[v]){
    if(nv.first==p) continue;
    paint(T,nv.first,v);
  }

}

int main(){

  //入力
  int N;
  cin>>N;

  Graph T(N+1);
  for(int i=0;i<N-1;++i){
    int u,v,w;
    cin>>u>>v>>w;
    T[u].push_back(make_pair(v,w));
    T[v].push_back(make_pair(u,w));
  }

  //0-1に距離0の辺を取っておく
    T[0].push_back(make_pair(1,0));
    T[1].push_back(make_pair(0,0));


  //1を白頂点として塗り分ける。color[i]はi番目の色(0は白、1は黒)
  color.assign(N+1,0);

  //1を頂点として探索するので1の親は0としておく
  paint(T,1,0);

  //出力
  for(int i=1;i<=N;++i){
    cout<<color[i]<<endl;
  }
}

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


Measured memory_bytes: 2100
/**
 * @author karayuu
 */

fun main(args: Array<String>) {
    val list = mutableListOf<Int>()

    var s = readLine()!!.toInt()
    var count = 2
    list.add(s)

    while (true) {
        if (s % 2 == 0) {
            s /= 2
        } else {
            s = 3 * s + 1
        }

        if (list.contains(s)) {
            println(count)
            return
        }
        list.add(s)
        count++
    }
}

Measured memory_bytes: 33784
N,M,K = [int(_n) for _n in input().split()]
A = [int(_n) for _n in input().split()]
B =[int(_n) for _n in input().split()]
sA = [0]*(N+1)
sB = [0]*(M+1)
for i in range(N):
    sA[i+1] = sA[i] + A[i]
for i in range(M):
    sB[i+1] = sB[i] + B[i]

res = 0
for i in range(N+1):
    Aread = sA[i]
    if Aread > K:
        break
    moku = K - Aread
    ok = 0
    ng = M+1
    while ng - ok > 1:
        mid = (ng+ok)//2
        if sB[mid] > moku:
            ng = mid
        else:
            ok = mid
    res = max(res, i+ok)
print(res)


Measured memory_bytes: 111844
#include <cstdio>
#include <iostream> 
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
 
using namespace std;
using ll = long long;
 
const ll INF = 1e9;
const ll MOD = 1e9 + 7;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };


int main()
{
    string s;
    int ans = 0, i, f;

    cin >> s;

    if(s[0] == 'B')f = 0;
    else f = 1;
    for(i = 1; i < s.size(); i++){
        if(s[i] == 'B'){
            if(f){
                ans++;
                f = 0;
            }
        }
        else{
            if(!f){
                ans++;
                f = 1;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 512
import itertools
import math
import fractions
import functools
n = int(input())
a = list(map(int, input().split()))
index = []
for i in range(n):
    index.append([a[i],i+1])
index.sort(key=lambda x: x[0])

for i in range(n):
    print(index[i][1], end=" ")
print("")


Measured memory_bytes: 93544
import scala.io.StdIn

object Main extends App {
  val n = StdIn.readLine()
  val d :Array[Int]  = StdIn.readLine().split(" ").map(_.toInt)

  var ans = 0

  d.zipWithIndex.foreach { i =>
    if (i._2 < d.length - 1) ans = ans + d.drop(i._2 + 1).map(_ * i._1).sum
  }

  println(ans)

}
  



Measured memory_bytes: 27304
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int dp[101010],a[105],b[105];
int n,w;
int main(){
  cin>>n>>w;
  rep(i,n)cin>>a[i]>>b[i];
  dp[0]=0;
  for(int i=1;i<=w;i++){
    dp[i]=dp[i-1];
    rep(j,n){
      if(dp[i-b[j]]+a[j]>dp[i]&&i-b[j]>=0){
        dp[i]=dp[i-b[j]]+a[j];
      }
    }
  }
  cout<<dp[w]<<endl;
  return 0;
}


Measured memory_bytes: 3148
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class ModTools:
    """ 階乗・逆元用のテーブルを構築する """

    def __init__(self, MAX, MOD):

        # nCrならn、nHrならn+rまで作る
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, -1, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse

    def nCr(self, n, r):
        """ 組み合わせ """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

    def nHr(self, n, r):
        """ 重複組み合わせ """

        # r個選ぶところにN-1個の仕切りを入れる
        return self.nCr(r+n-1, r)

    def nPr(self, n, r):
        """ 順列 """

        if n < r: return 0
        return self.fact[n] * self.inv[n-r] % self.MOD

N, M = MAP()

mt = ModTools(M+1, MOD)
acnt = mt.nPr(M, N)

bcnt = 0
for i in range(N+1):
    bcnt += mt.nCr(N, i) * mt.nPr(M-i, N-i) * (-1)**i
    bcnt %= MOD
ans = acnt * bcnt % MOD
print(ans)


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

int main(){
     int N,X = 0;
     cin >> N >> X;
     int m[N] ={0};
     int total = X;
     int Dmin = 100000;;
     for(int i = 0;i<N;i++){
         cin >> m[i];
         total -=m[i];
         Dmin = min(Dmin,m[i]);
     }
     total = total/Dmin;

     cout << total+N << endl;

    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")

#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll unsigned long long
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (ll)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)
//#define for(int i=0;i<n;i++) for(ll i=0;i<n;i++)
using namespace std;
//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
ll inf = 1e18, mod2 = 998244353, mod1 = 1e9 + 7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//const ll to[5]={0,4,6,7,9};
//const ll N=2*1e5+1;
const ll R=1e4;
//const ll to[7]={1,2,3,1,3,2,1};
//const ll tx[4]={0,0,-1,1};
//const ll ty[4]={-1,1,0,0};
const char rev_to[4]={'E','W','N','S'};
const ll N=2*1e5+4;
//set<int> lol2[26][26];
set<int>ab;
set<int>ba;
signed main(){
    fast_io;
    ll n;
    cin>>n;
    vector<ll>a(n);
    ll f=1,s=0;
    for(auto &z : a){
        cin>>z;
    }
    sort(all(a));
    bool ok=1;
    for(int i=0;i<n;i++){
        f*=a[i];
        if(f<s || f>inf){
            ok=0;
        }
        else{
            s=f;
        }
    }
    if(ok) cout<<f;
    else cout<<-1;
    return 0;
}
/*
    aa
    bb
    если WA , то чекер говно, поэтому почекай l8 строчку
    !x || !y x-проигрышная или выигрышная , y-колво таких позиций
    x==0 проигрышная
    y==0 четное проигрышных или четное выигрышных
    x==0 && y==0 четное проигрышных
*/


Measured memory_bytes: 3992
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
inline ll powt(ll a){
  if(!a)return 1;
  return powt(a-1)*10;
}
int main(){
  ll a,ans;
  cin>>a;
  ans=a;
  ll dig=(int)log10(a)+1;
  for(ll i=dig-1;i>0;i--){
    for(ll j=dig-i;j>=0;j--){
      if(i+j==dig||!j)ans+=(a/powt(j)%powt(i))<<(dig-i-1);
      else ans+=(a/powt(j)%powt(i))<<(dig-i-2);
    }
  }
  cout<<ans;
}

Measured memory_bytes: 256
num1 = input()
num1 = num1.split()
if(num1[1] <= num1[2]):
    print(num1[1]+" ", end="")
else:
    print(num1[2]+" ", end="")
if(int(num1[1])+int(num1[2])-int(num1[0]) <= 0):
    print("0")
else:
    print(int(num1[1])+int(num1[2])-int(num1[0]))

Measured memory_bytes: 3060
manhattan = lambda x,y: abs(x[0] - y[0]) + abs(x[1] - y[1])

def solve():
    n = int(input())
    table = [[0, 0, 0]] + [list(map(int, input().rstrip("\n").split())) for i in range(n)]

    for i in range(1, len(table)):
        t = (table[i][0] - table[i - 1][0] - manhattan(table[i - 1][1:], table[i][1:]))
        if t < 0 or t % 2 != 0:
            return "No"
    return "Yes"

print(solve())


Measured memory_bytes: 61272
from bisect import bisect_right
def main():
  s=input()
  t=input()
  n=len(t)
  m=len(s)
  lindex=[[] for _ in range(26)]
  for i in range(m):
    if s[i] in t:
      lindex[ord(s[i])-97].append(i)
  for i in range(n):
    if len(lindex[ord(t[i])-97])==0:
      print(-1)
      exit()
  cnt=0
  inde=-1
  for i in range(n):
    l=len(lindex[ord(t[i])-97])
    idx=bisect_right(lindex[ord(t[i])-97],inde)
    if l==idx:
      cnt+=1
      inde=lindex[ord(t[i])-97][0]
    else:
      inde=lindex[ord(t[i])-97][idx]
  return print(m*cnt+inde+1)
if __name__=='__main__':
  main()

Measured memory_bytes: 7668
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a,b;
    cin >> a >> b;
    cout << max(a-b,max(a+b,a*b)) << endl;
}

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

int main() {
    int n;
    cin >> n;
    vector<ll> v(n);
    for(int i = 0; i < n;++i){
        cin >> v[i];
    }
    // cout << "end" << endl;
    if(n <= 2){
        cout << "0" << endl;
        return 0;
    }
    sort(v.begin(),v.end());
    set<pair<int,pair<int,int>>> s;
    int ans = 0;
    for(int i = 0; i < n-2;++i){
        for(int j = i + 1;  j < n-1; ++j){
            for(int k = j+1; k < n; ++k){
                // cout << i << j << k << endl;
                if(v[i] + v[j] > v[k] && (v[i]!=v[j]) && (v[j] != v[k]) && (v[k]!=v[i])){
                    ans++;
                    // s.insert({v[i],{v[j],v[k]}});
                }
            }
        }
    }
    cout << ans
    << endl;
	return 0;
}


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

int main(void) {
  int N;
  cin >> N;
  vector<long long> a(N);
  long long sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    sum += a[i];
  }
  long long ans = INT_MAX;
  for (int i = 0; i < N - 1; i++) {
    sum -= 2 * a[i];
    ans = min(ans, abs(sum));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
n, q = gets.chomp.split.map(&:to_i)
s = gets
sum = [0] * (n + 1)

(n-1).times do |i|
  sum[i+1] += 1 if s[i]=='A' && s[i+1]=='C'
end
n.times{|i| sum[i+1] += sum[i] }

q.times do
  l, r = gets.chomp.split.map(&:to_i).map(&:pred)
  puts(sum[r]-sum[l])
end



Measured memory_bytes: 3196
import bisect
n = int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

a.sort()
b.sort()
c.sort()
sm = 0
for i in b:
    target = i
    a_idx = bisect.bisect_left(a,target)
    c_idx = bisect.bisect_right(c,target)
    sm += a_idx * (n-c_idx)

print(sm)

Measured memory_bytes: 29380
#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define fio freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define dsc [](int a,int b)->bool {return a>b;}
#define pb push_back
#define test int t; cin>>t;
#define MOD 998244353LL
#define all(x) (x).begin(),(x).end()

using namespace std;

ll nxt() { ll x; cin>>x; return x; }

int main()
{
    #ifndef ONLINE_JUDGE
        fio
    #endif
    IOS

    string s;
    cin>>s;
    int n = s.length();
    if(s[n-1] == 's') cout<<s<<"es"<<endl;
    else cout<<s<<"s"<<endl;

    return 0;
}


Measured memory_bytes: 3660
# include <iostream>
# include <cmath>
# include <vector>
# include <algorithm>
# include <string>
# include <set>
# include <map>
# include <bitset>
# include <queue>
# include <iomanip>

# define FILE
using namespace std;

const int N = 1e5 + 100;

int n, m, ans;
pair < int, int > jobs[N];
set < int > st;

int main()
{
    # ifdef FILEs
        freopen( "input.txt", "r", stdin );
        freopen( "output.txt", "w", stdout );
    # endif // FILE
    ios_base::sync_with_stdio( false );

    cin >> n >> m;
    for( int i = 1; i <= n; i ++ ){
        cin >> jobs[i].first >> jobs[i].second;
        swap( jobs[i].first, jobs[i].second );
    }
    sort( jobs+1, jobs+n+1 );
    reverse( jobs+1, jobs+n+1 );

    for( int i = 0; i < m; i ++ ){
        st.insert( i );
    }
    for( int i = 1; i <= n; i ++ ){
        set < int > :: iterator it = st.upper_bound( m - jobs[i].second );
        if( it != st.begin() ){
            it--;
            st.erase( *it );
            ans += jobs[i].first;
        }
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5760
N=int(input())
T,A=map(int,input().split())
H=list(map(int,input().split()))
mylist=[]
for i in range (N):
  C=T-H[i]*0.006
  D=abs(A-C)
  mylist.append(D)
E=mylist.index(min(mylist))
F=E+1
print(F)

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

int main() {
    int A,B;
    cin >>A>>B;
    if(A>B){
        int maximum =max(A-1,B);
        cout << A+ maximum <<endl;
    }
    else if (A<B){
        int maximum = max(A,B-1);
        cout << B + maximum <<endl;
    }
    else cout << 2*B <<endl;
}

Measured memory_bytes: 256
import Data.List
import Control.Monad

day :: [String]
day = ["SUN", "MON", "TUE", "WED", "WED", "THU", "FRI", "SAT"]

main = print =<< ((pure calc) <*> getInts)

getInt :: IO Int 
getInt = (pure read) <*> getLine

getInts :: IO [Int]
getInts = replicateM 4 getInt

getx :: [Int] -> Int
getx [n, k, x, _] = (*) x $ min n k

gety :: [Int] -> Int
gety [n, k, _, y] = (*) y $ max 0 $ n - k

calc :: [Int] -> Int
calc val = (getx val) + (gety val)


Measured memory_bytes: 508
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
using namespace std;

int main(){
    int X,t;cin >> X>>t;
    if (X>t){
        cout << X - t << endl;
    } else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
bool x_[(int) 4e4], y_[(int) 4e4];
bool *x = x_ + (int) 2e4;
bool *y = y_ + (int) 2e4;
bool xd_[(int) 4e4], yd_[(int) 4e4];
bool *xd = xd_ + (int) 2e4;
bool *yd = yd_ + (int) 2e4;
signed main() {
  cin.tie(0); ios::sync_with_stdio(false);
  string s; cin >> s;
  int n = s.size();
  int xs, ys; cin >> xs >> ys;
  int d = 0;
  vector<vector<int>> a(2, vector<int>());
  int t = 0, i = 0;
  while (s[i] == 'F') {
    xs--;
    i++;
  }
  for (; i < n; i++) {
    if (s[i] == 'T') {
      if (t) a[d].push_back(t);
      d = 1 - d;
      t = 0;
    } else if (i == n - 1) a[d].push_back(t + 1); 
    else t++;
  }
  for (auto q : a[0]) cerr << q << ' ';cerr << '\n';
  for (auto q : a[1]) cerr << q << ' ';cerr << '\n';
  x[0] = y[0] = true;
  for (auto&& i : a[0]) {
    for (int j = -16000; j <= 16000; j++) if (x[j]) xd[j + i] = xd[j - i] = true;
    for (int j = -16000; j <= 16000; j++) {x[j] = xd[j]; xd[j] = false;}
  }
  for (auto&& i : a[1]) {
    for (int j = -8000; j <= 8000; j++) if (y[j]) yd[j - i] = yd[j + i] = true;
    for (int j = -8000; j <= 8000; j++) {y[j] = yd[j]; yd[j] = false;}
  }
  cout << (x[xs] and y[ys] ? "Yes" : "No") << '\n';
  return 0;
}

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> T(N);
    for(int i = 0; i < M; ++i) {
        int k; cin >> k;
        for(int j = 0; j < k; ++j) {
            int s; cin >> s;
            T[--s] |= 1 << i;
        }
    }
    int pmask = 0;
    for(int i = 0; i < M; ++i) {
        int p; cin >> p;
        if(p) pmask |= 1 << i;
    }
    auto rec = [&](auto &&rec, int i, int mask) -> int {
        if(i == N) return mask == pmask;
        return rec(rec, i + 1, mask) + rec(rec, i + 1, mask ^ T[i]);
    };
    cout << rec(rec, 0, 0) << '\n';
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<vector>
#include<iostream>
#include<sstream>
#include<fstream>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
/*freopen{"input.txt","r",stdin};
freopen{"output.txt","w",stdout};*/
#define mp make_pair
#define pb push_back
const int INF=1000*1000*1000;
const int maxn=2e5; 
typedef long long ll;
typedef long double ld;
typedef pair<int,int>PII;
//priority_queue <int,vector<int>,greater<int> > q1;  //从小到大 
//priority_queue <int,vector<int>,less<int> >q2;  //从大到小 

//set multiset vector queue priority_queue map multimap pair string structure 

//枚举 思维 贪心 搜索 模拟 预处理 二分 排序 

int main(){
	//ios_base::sync_with_stdio(0);
    //cin.tie(0);
    //cout.tie(0);
	ll n,a,b;
	cin>>n>>a>>b;
	if(a==b){
		cout<<0;
	}
	else{
		ll l=min(a,b);
		ll r=max(a,b);
		if((r-l)%2==0){
			cout<<(r-l)/2;
		}
		else{
			ll t1=(a-1)+(b-1)+1;
			ll t2=(n-a)+(n-b)+1;
			cout<<min(t1,t2)/2;
		}	
	}
	return 0;
}


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

int main(void)
{
	long long num = 100000, day;
	cin >> day;

	for (int i = 0; i < day; i++) {
		num *= 1.05;
		if (num % 1000) num = num - (num % 1000) + 1000;
	}
	cout << num << endl;
	
	return 0;
}

Measured memory_bytes: 1156
#include<stdio.h>
int main(void){
	int n, x, i;
	scanf("%d",&n);
	for(i=1; i<=n; i++){
		x=i;
		if(x%3==0){
			printf(" %d", i);
		}else if(x%10==3){
			printf(" %d", i);
		}else{
			while(x){
				x/=10;
				if(x%10==3){
					printf(" %d", i);
					break;
				}
			}
		}
	}
	
	printf("\n");
	
	
	return 0;
}

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

int main(){
	int n, v[5];
	
	cin >> n;
	
	for(int i=0; i<n; i++){
		for(int j=0; j<3; j++){
			cin >> v[j];
		}
		
		sort(v, v+3, greater<int>());
		
		if(v[0]*v[0] == v[1]*v[1] + v[2]*v[2]){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}

	}
	
}

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

long long gcd(long long a, long long b) {
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
int main() {
  long long a, b;
  cin>>a>>b;
  long long g = gcd(a, b);

  if (g == 1) {
    cout<<1<<endl;
    return 0;
  }
  set<int> c;
  for (int i=2; i<= sqrt(g); i++) {
    if (g % i == 0) {
      c.insert(i);
      while (g % i == 0) {
        g /= i;
      }
    }
  }
  if (c.find(g) == c.end() && g != 1) {
    c.insert(g);
  }
  cout<<c.size()+1<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod;
#define mul(a,b) a=a*b%mod;
ll n,a[1010];
int main(){
  cin>>n;
  ll sa=0,sb=0;
  for(int i=0;i<n;i++){
      cin>>a[i];
      if(i%2==0)sa+=max(0LL,a[i]);
      if(i%2==1)sb+=max(0LL,a[i]);
  }
  vector<ll> ans;
  if(sb>sa){
      ans.push_back(1);
      for(int i=0;i<n-1;i++)a[i]=a[i+1];
      n--;
      swap(sa,sb);
  }
  if(n%2==0){
      ans.push_back(n);
      n--;
  }
  if(sa==0){
      ll ma=-1e17,pnt=-1;
      for(int i=0;i<n;i++){
          if(a[i]>ma)ma=a[i],pnt=i;
      }
      for(int i=n;i>1+pnt;i--)ans.push_back(i);
      for(int i=0;i<pnt;i++)ans.push_back(1);
      sa=ma;
  }
  else{
      int p=0;
      for(int i=0;i<n;i+=2){
          if(a[i]>0)break;
          p=i+2;
          ans.push_back(1);
          ans.push_back(1);
      }
      for(int i=p+2;i<n;i+=2){
          if(a[i]>0)ans.push_back(2);
          else ans.push_back(3);
      }
      if(ans.back()==3)ans.push_back(2);
  }
  cout<<sa<<endl;
  cout<<ans.size()<<endl;
  for(auto t:ans)cout<<t<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
using namespace std;
static const LL INF = 1LL<<60LL;
typedef pair<int,int> pii;

int n,m;
int C[2016],D[2016];
int res;
int place=1;

int main(){
    while(1){
        cin>>n>>m;
        if(n==0&&m==0)break;
        memset(C,0,sizeof(C));
        memset(D,0,sizeof(D));
        for(int i=1;i<=n;++i){
            cin>>C[i];
        }
        for(int i=1;i<=m;++i){
            cin>>D[i];
        }
        for(int i=1;i<=m;++i){
            place+=D[i];
            place+=C[place];
            res++;
            if(place>=n)break;
        }
        cout<<res<<endl;
        res=0;
        place=1;
    }
}

Measured memory_bytes: 1176
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define BIG 1000000010
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
typedef long long int ll;


int main(){
  int n,k;
  cin>>n>>k;
  char s;
  int a=0;
  deque<char> d;
  rep(i,n){
    cin>>s;
    d.push_back(s);
  }
  rep(i,k){
    if(d.front()-(a%2)=='A'){
      d.pop_front();
      d.push_front('B'-(a%2));
    }
    else{
      a++;
      d.pop_front();
      if(a%2) d.push_back('B');
      else d.push_back('A');
    }
    if(a>n){
      if(a%2==1){
	rep(k,d.size()){
	  if(d[k]=='A') d[k]='B';
	  else d[k]='A';
	}
      }
      if(n%2==0){
	rep(j,n){
	  
	  if(j%2==0 && d[j]!='B') break;
	  else if(j%2==1 && d[j]!='A') break;
	  else if(j==n-1) i=BIG;
	}
      }
      else{
	repi(j,1,n){
	  if(j%2==1 && d[j]!='B') break;
	  else if(j%2==0 && d[j]!='A') break;
	  else if(j==n-1) i=k-1-((k-1-i)%2);
	}
      }
    }
  }
  if(a<=n){
    if(a%2==1){
      rep(k,d.size()){
	if(d[k]=='A') d[k]='B';
	else d[k]='A';
      }
    }
  }
  rep(i,n){
    cout<<d[i];
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i = 0; i < (n); i++)
typedef long long ll;
// Welcome to my source code!

int main() {
    string s;
    cin >> s;
    int cnt = 0, maxc = 0;
    REP(i, s.size()) {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            cnt++;
            maxc = max(maxc, cnt);
        } else cnt = 0;
    }
    cout << maxc << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		 String O = sc.next();

		 String B = sc.next();
		 
		 String[] strO = O.split("");
		 String[] strB = B.split("");
		 
		 String ans[] = new String[strO.length+strB.length];
		 
		 for(int i=0; i<strB.length; i++){
			ans[2*i] = strO[i];
			ans[2*i+1] = strB[i];
		 }
		 if(strO.length>strB.length){
			 ans[2*strB.length] = strO[strO.length-1];
		 }
	
		 for(int i=0; i<ans.length; i++){
			 System.out.print(ans[i]);
		 }
		 
	}

}


Measured memory_bytes: 23508
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,num;
  int kaibun = 0;
  
  cin >> A >> B;
  
  while (A <= B) {
    num = A;
    if (num / 10000 == num % 10) {
      if ( num / 1000 % 10 == num / 10 % 10 ) {
         kaibun++;   
      }
    }
    A++;
  }  

  cout << kaibun << endl;   
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  long long N;
  long long  maxc = 0;
  long long cnt = 0;

  cin >> N;

  vector<long long> H(N);
  for(int i = 0; i < N; i++){
    cin >> H[i];

    if(i>0){
      //連続降下可能数カウント
      if(H[i-1] >= H[i]){
        cnt++;
        maxc = max(maxc, cnt);
      }else{
        cnt = 0;
      }
    }
  }
  cout << maxc << endl;

}


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

#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define MOD 1000000007

#define trace1(x)                    cout <<#x<<": "<<x<< endl;
#define trace2(x, y)                 cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<< endl;
#define trace3(x, y, z)              cout <<#x<<": "<<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl;
#define trace4(a, b, c, d)           cout <<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl;

typedef long long ll;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    ll nw=(c*d)/(__gcd(c,d));
    cout<<(b-a+1)-((b/c)+(b/d)-((a-1)/c)-((a-1)/d)-(b/nw)+((a-1)/nw));
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"strconv"
)

func numArrayToString(iary []int) []string {
	ary := make([]string, len(iary))
	for i, v := range iary {
		ary[i] = strconv.Itoa(v)
	}
	return ary
}

type point struct {
	x int
	y int
}

type area struct {
	minPoint point
	maxPoint point
}

func circleArea(x int, y int, r int) area {
	return area{point{x - r, y - r}, point{x + r, y + r}}
}

func rectangleArea(w int, h int) area {
	return area{point{0, 0}, point{w, h}}
}

func isInclude(a area, b area) bool {
	if a.minPoint.x <= b.minPoint.x && a.minPoint.y <= b.minPoint.y && a.maxPoint.x >= b.maxPoint.x && a.maxPoint.y >= b.maxPoint.y {
		return true
	}
	return false
}

func isIncludeStr(a area, b area) string {
	if isInclude(a, b) {
		return "Yes"
	}
	return "No"
}

func main() {
	var w, h, x, y, r int
	fmt.Scanf("%d %d %d %d %d", &w, &h, &x, &y, &r)
	rect := rectangleArea(w, h)
	circle := circleArea(x, y, r)

	fmt.Println(isIncludeStr(rect, circle))
}



Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int n,m;
int main(){
  cin >> n >> m;
  vector<vector<int> > s(m);
  for(int i=0 ; i<m ; i++){
    int k;  cin >> k;
    for(int j=0 ; j<k ; j++){
      int x;  cin >> x; --x;
      s[i].push_back(x);
    }
  }
  vector<int> p(m);
  for(int i=0 ; i<m ; i++){
    cin >> p[i];
  }
  long long res = 0;
  for(int bit=0 ; bit< (1<<n) ; bit++){
    bool ok = true;
    for(int i=0 ; i<m ; i++){
      int con = 0;
      for(auto v : s[i]){
          if(bit & (1<<v))  con++;
      }
      if(con%2 != p[i]) ok = false;
    }
    if(ok)  res++;
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstring>
int T, N, K, X[100000 + 10], A[100000 + 10];
using namespace std;
int main()
{
    cin >> T;
    for (int t = 0; t < T; ++t)
    {
        cin >> N;
        cin >> K;
        for (int i = 0; i < N; ++i)
            cin >> X[i];
        for (int i = 0; i + 1 < N; ++i)
        {
            A[i] = X[i + 1] - X[i];
        }
        sort(A, A + N - 1);
        int result = 0;
        if (N > K)
        {
            for (int i = 0; i < N - K; i++)
            {
                result += A[i];
            }
        }
        cout << result << endl;
    }
    return 0;
}


Measured memory_bytes: 3916
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
	sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
	{
sim > struct rge
{
	c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug
{
#ifndef LOCAL
	~debug()
	{
		cerr << endl;
	}
	eni(!=) cerr << boolalpha << i;
	ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
	ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d)
{
	*this << "[";
	for (auto it = d.b; it != d.e; ++it)
		*this << ", " + 2 * (it == d.b) << *it;
	ris << "]";
}
#else
	sim dor(const c &)
	{
		ris;
	}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
template <typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define ld long double
#define pb push_back
#define mp make_pair
#define in insert
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define sz(v) (int)(v.size())
#define all(x) x.begin(), x.end()
#define prec fixed << setprecision(12)
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define repr(i, a, b) for (int i = a; i >= b; i--)
#define test  \
	int t;    \
	cin >> t; \
	while (t--)
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef set<int> si;
typedef map<int, int> mii;
typedef vector<pii> vpi;
int _x[] = {0, 0, -1, 1, -1, 1, -1, 1};
int _y[] = {-1, 1, 0, 0, 1, -1, -1, 1};

void solve()
{
	int n;
	cin >> n;
	vi v(n);
	rep(i, 0, n-1) cin >> v[i];
	int ans =0 ;
	rep(i, 1, n-1){
		if(v[i] < v[i-1]){
			ans += v[i-1]-v[i];
			v[i] = v[i-1];
		}
	}
	cout << ans;
}

int32_t main()
{
	ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	cin.tie(NULL);
	// test
	solve();
	return 0;
}


Measured memory_bytes: 4760
import scala.io.StdIn.{readInt, readLine}
object Main {
    def main(args: Array[String]): Unit = {
        readInt
        val arr = readLine.split(" ").map(_.toInt)
        println(countingSort(arr).mkString(" "))
    }
    def countingSort(arr: Array[Int]): Array[Int] = {
        val count = new Array[Int](10001)
        val ret = new Array[Int](arr.length)
        arr.foreach { i => count(i) = count(i) + 1}
        (0 until count.length).foldLeft(0) { (sum, i) => 
            count(i) = sum + count(i)
            count(i)
        }
        arr.reverse.foreach { i =>
            count(i) -= 1
            ret(count(i)) = i
        }
        ret
    }
}


Measured memory_bytes: 455376