akhauriyash/Code-Regression huggingface dataset:
loop do
    n = gets.to_i
    break if n == 0
    a = [0] * n
    f = 0
    gets.chomp.each_char.with_index do |c, i|
        if c == ?M
            a[i % n] += 1
        elsif c == ?L
            a[i % n] += 1 + f
            f = 0
        else
            f += 1 + a[i % n]
            a[i % n] = 0
        end
    end
    puts (a.sort + [f]) * ' '
end


Measured memory_bytes: 6880
S=input()
T=input()
cnt=[]
if len(S)==len(T):
    kazu=0
    for i in range(len(S)):
        if S[i]!=T[i]:
            kazu+=1
    cnt.append(kazu)


for i in range(len(S)-len(T)):
    count=0
    kari=S[i:i+len(T)]
    for j in range(len(T)):
        if kari[j]!=T[j]:
            count+=1
    cnt.append(count)
print(min(cnt))

Measured memory_bytes: 9068
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(n) scanf("%d",&n);
#define PI acos(-1.0)
#define sl(n) scanf("%lld",&n);
#define sf(n) scanf("%lf",&n);
#define ss(n) scanf("%s",n);
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define forc(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define sor(n) sort(n.begin(),n.end())
#define sorcmp(n) sort(n.begin(),n.end(),cmp)
#define rev(n) reverse(n.begin(),n.end())
#define pi(x)  prllf("%d",x);
#define pl(x)  prllf("%lld",x);
#define pf(x)  prllf("%.10lf",x);
#define ps(x)  prllf("%s",x);
#define en() prllf("\n");
#define random_shuffle(r...)random_shuffle(r,[](int _){return rand()%_;})
#define SQR(a) (a)*(a)
#define mod 100000007
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);}
template <typename T> T POW(T B,T P){ if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return SQR(POW(B,P/2));}
ll powmod(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%mod;a = a*a%mod;b >>= 1;}return ans;}
ll prime[1000000];bool visprime[10000000];
void sieve(){ll k=0;for(ll i=2;i*i<=1000000;i++){for(ll j=i*i;j<=1000000;j+=i){visprime[j]=true;}}for(ll i=2;i<=1000000;i++){if(visprime[i]==false) prime[k++]=i;}}


int main()
{

    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        cin>>arr[i];
        int cnt=0,mx=0;
    for(int i=0;i<n-1;i++)
    {
         //cout<<arr[i]<<" "<<arr[i+1]<<endl;
        if(arr[i]>=arr[i+1])
        {
            cnt++;
            if(i==n-2) mx=max(mx,cnt);
        }
        else
        {

             mx=max(mx,cnt);
            cnt=0;

        }
       //cout<<cnt<<endl;
    }
    cout<<mx<<endl;




}
























Measured memory_bytes: 640
<?php
fscanf(STDIN, "%d", $N);
$S = [];
for ($i = 0; $i < $N; $i++) {
    fscanf(STDIN, "%s", $S[]);
}
$sum = array_count_values($S);
$e = ['AC', 'WA', 'TLE', 'RE'];
foreach ($e as $f) {
    printf("%s x %d\n", $f, $sum[$f] ?? 0);
}


Measured memory_bytes: 25336
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef pair<int,int> P;

int n, m;
int e[20][20];

int main(){
	cin >> n >> m;
	rep(i,n) rep(j,n) e[i][j] = INF;
	rep(i,n) e[i][i] = 0;
	rep(i,m){
		int x[4];
		string str;
		cin >> str;
		int tmp = 0, cnt = 0;
		rep(j,str.size()){
			if(str[j] != ','){
				tmp *= 10;
				tmp += str[j]-'0';
			} else{
				x[cnt] = tmp;
				cnt++; tmp = 0;
			}
			if(j == str.size()-1) x[cnt] = tmp;
		}
		x[0]--; x[1]--;
		e[x[0]][x[1]] = x[2];
		e[x[1]][x[0]] = x[3];
	}
	rep(k,n) rep(i,n) rep(j,n) e[i][j] = min(e[i][j],e[i][k]+e[k][j]);
	int y[4];
	string str; cin >> str;
	int tmp = 0, cnt = 0;
	rep(j,str.size()){
		if(str[j] != ','){
			tmp *= 10;
			tmp += str[j]-'0';
		} else{
			y[cnt] = tmp;
			cnt++; tmp = 0;
		}
		if(j == str.size()-1) y[cnt] = tmp;
	}
	y[0]--; y[1]--;
	cout << y[2]-y[3]-e[y[0]][y[1]]-e[y[1]][y[0]] << endl;
	
}

Measured memory_bytes: 1204
def bin_src_l(arr, key):
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = (l + r) // 2
    if arr[mid] > key:
      r = mid - 1
    else:
      l = mid + 1
  
  if l < len(arr):
    return l
  else:
    return None

def bin_src_s(arr, key):
  l = 0
  r = len(arr) - 1
  while l <= r:
    mid = (l + r) // 2
    if arr[mid] >= key:
      r = mid - 1
    else:
      l = mid + 1
  
  if r >= 0 :
    return r
  else:
    return None


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A = sorted(A)
C = sorted(C)

sum = 0
for b in B:
  a = bin_src_s(A, b)
  c = bin_src_l(C, b)
  a = a + 1 if a is not None else None
  c = N - c if c is not None else None
  if a is not None and c is not None:
    sum += a * c
  
print(sum)

Measured memory_bytes: 29384
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
 
using namespace std;
 
typedef long long ll;
 
#define sz size()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(c) (c).begin(), (c).end()
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define per(i,a,b) for(ll i=b-1LL;i>=(a);--i)
#define clr(a, b) memset((a), (b) ,sizeof(a))
#define ctos(c) string(1,c)
#define print(x) cout<<#x<<" = "<<x<<endl;
 
#define MOD 1000000007

vector<vector<ll> > vv;
vector<vector<ll> > vvp;
map<pair<ll,ll>,ll> ma;

ll dfs(ll a, ll p, ll b, ll c){
  if(vv[a].sz==1&&p!=-1){
    if(a==c)return 1;
    return 0;
  }
  ll ret = 0;
  rep(i,0,vv[a].sz){
    if(vv[a][i]==p)continue;
    ll ret1 = dfs(vv[a][i],a,b,c);
    if(ret1==1){
      ll a1 = vv[a][i];
      ll b1 = a;
      if(a1>b1)swap(a1,b1);
      vvp[ma[mp(a1,b1)]].pb(b);
    }
    ret |= ret1;
  }
  if(a==c)ret = 1;
  return ret;
}

ll dp[55][1<<20];

int main(){
  ll n;
  cin>>n;
  vector<vector<ll> > vv_(n,vector<ll>());
  vv = vv_;
  vector<vector<ll> > vvp_(n-1,vector<ll>());
  vvp = vvp_;
  vector<pair<ll,ll> > vp;
  rep(i,0,n-1){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    vv[a].pb(b);
    vv[b].pb(a);
    if(a>b)swap(a,b);
    vp.pb(mp(a,b));
    ma[mp(a,b)] = i;
  }
  ll m;
  cin>>m;
  vector<pair<ll,ll> > vm;
  rep(i,0,m){
    ll a,b;
    cin>>a>>b;
    a--;b--;
    vm.pb(mp(a,b));
  }
  rep(i,0,vm.sz){
    ll s = vm[i].fi;
    ll g = vm[i].se;
    dfs(s,-1,i,g);
  }
  vector<ll> v1;
  rep(i,0,vp.sz){
    ll a = vp[i].fi;
    ll b = vp[i].se;
    ll bit = 0;
    rep(j,0,vvp[ma[mp(a,b)]].sz){
      ll c = vvp[ma[mp(a,b)]][j];
      bit |= 1LL<<c;
    }
    v1.pb(bit);
  }
  clr(dp,0);
  dp[0][0] = 1;
  rep(i,0,n-1){
    ll a = vp[i].fi;
    ll b = vp[i].se;
    ll bit = v1[i];
    rep(j,0,1<<m){
      dp[i+1][j|bit] += dp[i][j];
      dp[i+1][j] += dp[i][j];
    }
  }
  cout << dp[n-1][(1<<m)-1] << endl;
  return 0;
}

Measured memory_bytes: 450816
#include <stdio.h>
typedef long long ll;

int main(void) {
  ll n, x, y, i, j, tmp;
  scanf("%lld%lld%lld", &n, &x, &y);
  --x, --y;
  ll ans[n];
  for(i = 0; i < n; ++i) ans[i] = 0;
  for(i = 0; i < n; ++i) for(j = i + 1; j < n; ++j) {
    if(j <= x) ans[j - i]++;
    else if(i >= y) ans[j - i]++;
    else if(i <= x) {
      if(j >= y) ans[x - i + j - y + 1]++;
      else {
        tmp = x - i + y - j + 1;
        ans[tmp < j - i ? tmp : j - i]++;
      }
    } else {
      if(y >= j) {
        tmp = i - x + y - j + 1;
        ans[tmp < j - i ? tmp : j - i]++;
      } else {
        tmp = i - x + j - y + 1;
        ans[tmp < j - i ? tmp : j - i]++;
      }
    }
  }
  for(i = 1; i < n; ++i) printf("%lld\n", ans[i]);
  return 0;
}

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

ll N,a,ans;

int main(void){
    cin >> N;
    rep(i,N){
        cin >> a;
        while(a%2==0){a/=2;ans++;}
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readA(T)(size_t n,ref T[]t){t=new T[](n);auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int[] a; readA(3, a);

  a.sort();

  writeln(a[0]*a[1]/2);
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <map>
using namespace std;
const int MAXN = 30;
typedef long long LL;
const LL mod = 998244353;
int main()
{
    int n, k;
    scanf("%d %d",&n, &k);
    LL sum=0;
    if(k==0)
    {
        printf("%lld\n", (LL)n*n);
        return 0;
    }
    for(int i=k+1;i<=n;++i)
    {
        sum+=n/i*(i-k);
        if(n%i!=0&&n%i>=k)
        {
            sum+=n%i-k+1;
        }
    }
    printf("%lld\n", sum);
    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = n // 1000
b = n // 100 - a * 10
c = n // 10 - a * 100 - b * 10
d = n - a * 1000 - b * 100 - c * 10
yet = True
if a+b+c+d==7 and yet:
    print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
    yet = False
if a+b+c-d==7 and yet:
    print(str(a)+'+'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
    yet = False
if a+b-c+d==7 and yet:
    print(str(a)+'+'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
    yet = False
if a+b-c-d==7 and yet:
    print(str(a)+'+'+str(b)+'-'+str(c)+'-'+str(d)+'=7')
    yet = False
if a-b+c+d==7 and yet:
    print(str(a)+'-'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
    yet = False
if a-b+c-d==7 and yet:
    print(str(a)+'-'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
    yet = False
if a-b-c+d==7 and yet:
    print(str(a)+'-'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
    yet = False
if a-b-c-d==7 and yet:
    print(str(a)+'-'+str(b)+'-'+str(c)+'-'+str(d)+'=7')    
    yet = False

Measured memory_bytes: 3192
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define each(a,x) for(auto a : (x))
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) ((a) = min((a),(b)))
#define chmax(a,b) ((a) = max((a),(b)))
#define in_range(x,l,r) ((l)<=(x) && (x)<(r))
#define fs first
#define sc second
#define pb push_back
#define sz size() 
#define MP make_pair
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<string> vs;

const static int INF = 1e8;
const static D EPS = 1e-8;

int main(){
  int n,m;
  cin >> n >> m;
  vector<int> b(n,1), r(n,0);
  r[0] = 1;

  rep(i,m){
    int x,y;
    cin >> x >> y; x--; y--;
    if(r[x]){
      r[y] = 1;
      if(b[x] == 1) r[x] = 0;
    }
    b[x]--; b[y]++;
  }

  cout << accumulate(all(r),0) << endl;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#include <stdio.h>
#include <set>
using namespace std;

void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
void setIO(string s = ""){
	unsyncIO();
	if(s.size()){
		setIn(s + ".in");
		setOut(s + ".out");
	}
}


#define ll long long
const ll mod = 1e9 + 7;
const int MX = 1000005;

int n, cnt[MX];
int gg[MX], v[MX];

int main(){
	setIO();
	cin >> n;
	for(int i = 0; i < n; i ++) cin >> gg[i];
	int ii = 0;
for(int j = 0; j < n; j ++) if(gg[j] != 1) v[ii ++] = gg[j];
	bool lol = false;
	if(ii != n) lol = true;
	n = ii;
	if(n <= 100000){
		for(int i = 0; i < n; i ++){
			for(int j = 1; j * j <= v[i]; j ++) if(v[i] % j == 0){
				if(j != 1) cnt[j] ++;
				if(j != v[i] / j && v[i]/j != 1) cnt[v[i]/ j] ++;
			}
		}
		bool ye = true;
		for(int i = 0; i < MX;i ++)
			if(cnt[i] > 1) ye = false;
		if(ye) {
			cout << "pairwise coprime\n";
			return 0;
		}
	}

	int gg = v[0];
	for(int i= 1; i < n; i ++) gg = __gcd(gg, v[i]);
	if(gg == 1 || lol) cout << "setwise coprime\n";
else cout << "not coprime\n";
}

Measured memory_bytes: 11468
#include<iostream>
#include<vector>
#include<string>
#include<map>

#define REP(i,j,k) for( int i=j; i<k; i++ )
#define rep(i,j) REP(i,0,j)

using namespace std;

typedef long int LI;

int main(){
	
	int a, b, t;
	
	cin >> a >> b >> t;
	
	cout << t/a*b << endl;
	
	return 0;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_dec_float.hpp>
using namespace std;
namespace mp = boost::multiprecision;
 
int main(){
    mp::cpp_dec_float_100 a, b, c;
    cin >> a >> b >> c;

    if(mp::sqrt(a) + mp::sqrt(b) < mp::sqrt(c))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

}

Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
//kaewasuretyuui
typedef long long ll;
#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
//#define mt make_tuple
//typedef tuple<int,int,int> tp;
//typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
//nCr mod m
#define MOD 1000000007
#define M 1000000
vector<ll> fact;
bool h=false;
void init(){
	h=true;
	fact=vector<ll>(M);
	fact[0]=fact[1]=1;
	loop(i,2,M)fact[i]=fact[i-1]*i%MOD;
}
// a^b mod MOD
ll powmod(ll a,ll b,ll m=MOD){
	ll out=1;
	ll p=a%m;
	while(b){
		if(b&1)out=out*p%m;
		p=p*p%m;
		b>>=1;
	}
	return out;
}
//nCr
ll nCr(ll n,ll r,ll m=MOD){
	if(!h)init();
	if(n<0||r<0||n<r)return 1;//??????
	ll out=fact[n]*powmod(fact[r]*fact[n-r]%m,m-2,m)%m;
	return out;
}
int n;
vi in;
pii f(int l,int r,int a){
	int mi=inf;
	loop(i,l,r)mi=min(mi,in[i]);
	
	vi t={l-1};
	loop(i,l,r)if(in[i]==mi)t.pb(i);
	t.pb(r);
	vp in;
	
	int w=r-l;
	rep(i,t.size()-1)if(t[i]+1-t[i+1])in.pb(f(t[i]+1,t[i+1],mi)),w-=t[i+1]-t[i]-1;
	
	int b=powmod(2,mi-a,MOD),c=powmod(2,w,MOD),d=(MOD+powmod(2,mi-a,MOD)-2)%MOD;
	rep(i,in.size()){
		(b*=in[i].first)%=MOD;
		(c*=in[i].first+in[i].second)%=MOD;
		(d*=in[i].first)%=MOD;
	}
	return {b,(c+d)%MOD};
}
signed main(){
	init();
	cin>>n;
	in=vi(n);
	rep(i,n)cin>>in[i];
	pii a=f(0,n,0);
	cout<<a.second<<endl;
}

















Measured memory_bytes: 8064
#最小コストソート
n = int(input())
A = list(map(int, input().split()))
#整列
B = sorted(A)
#サイクルに採用されたか否か
C = [0 for _ in range(n)]
CNT = 0
minA = B[0]

for i in range(n):
    #正しい位置にいるか
    if A[i] == B[i]:
        C[i] == 1
    #サイクルに採用済みか
    elif C[i] == 0:
        cyc = []
        ind = i
        #サイクル作成
        while C[ind] == 0:
            a = A[ind]
            cyc.append(a)
            C[ind] = 1
            ind = B.index(a)
        #2種のコスト計算
        mincyc = min(cyc)
        cost1 = sum(cyc) + (len(cyc) - 2) * mincyc
        cost2 = sum(cyc) + mincyc + (len(cyc) + 1) * minA
        if cost1 > cost2:
            CNT += cost2
        else:
            CNT += cost1
    else:
        pass
print(CNT)


Measured memory_bytes: 5632
import sys


def input():
    return sys.stdin.readline()[:-1]

# N = int(input())
# A = [int(x) for x in input().split()]
# a, b, c = map(int, input().split())
# name1 = str(input())
# alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}

a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a,b)+min(c,d))

Measured memory_bytes: 3060
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))

using namespace std;

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

const ll mod=1e9+7;

int main(){
    ll n,m;
    cin >> n >> m;
    n--; m--;
    cout << n*m << endl;
    return 0;
} 


Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
bool cmp(int a,int b)
{
	return a>b;
}
int main()
{
	int n;
	cin>>n;
	int a[n];
	for(int i=0;i<=n;i++)
	cin>>a[i];
	sort(a,a+n,cmp);
	long long s1=0,s2=0;
	for(int i=0;i<n;i+=2)
	{
		s1+=a[i];
	}
	for(int i=1;i<n;i+=2)
	{
		s2+=a[i];
	}
	cout<<s1-s2;
	return 0;
}

Measured memory_bytes: 256
n,a, b = map(int, input().split()) 
if a>0:
    if n-n//(a+b)*(a+b)>a:
        print(n//(a+b)*a+a)
    else:
        print(n//(a+b)*a+n-n//(a+b)*(a+b))
else:
    print(0)


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

char s[1010000];
int main()
{
	scanf("%s", s);
	int n = strlen(s);
	long long ans = 0, S = 0;
	for(int i = n - 1; i >= 0; i--)
	{
		if(s[i] == 'W') S++;
		else ans += S;
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#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__) << ""
#define arr array
using ll = long long;
const int INF = 1e9 + 5;
const int N = 1e6 + 5;

//dp[i] - maximum value of items with total weight
int main() {
	int n,W;
	scanf("%d%d", &n, &W);
	vector<long long> dp(W + 1,0); 
	
	for(int i = 0; i < n; i++) {
		int weight,value;
		scanf("%d%d", &weight, &value);
		for(int weight_already = W - weight; weight_already >= 0; weight_already--) {
			dp[weight_already + weight] = max(dp[weight_already + weight], value + dp[weight_already]);
		}
	}
	long long ans = 0;
	for(int i = 0; i <= W; i++) {
		ans = max(ans, dp[i]);
	}
	
	cout << ans << "\n";

    return 0;
}




Measured memory_bytes: 4060
using System;

namespace ABC088A
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            int A = int.Parse(Console.ReadLine());
            int remind = N - (int)(N / 500) * 500;
            if (remind <= A){
                Console.WriteLine("Yes");
            } else {
                Console.WriteLine("No");
            }
        }
    }
}


Measured memory_bytes: 11092
/*
ID: espr1t
TASK: 
KEYWORDS: 
*/

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;
FILE* in = stdin; FILE* out = stdout;

const int MAX = 200002;

int n;
char a[MAX];

long long solve() {
    long long ans = 0;
    long long cntA = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] == 'A') {
            cntA++;
            continue;
        } else {
            if (a[i] == 'B') {
                if (i + 1 < n && a[i + 1] == 'C') {
                    ans += cntA;
                    i++;
                    continue;
                } else {
                    cntA = 0;
                }
            } else {
                cntA = 0;
            }
        }
    }
    /*
    for (int i = 0; i + 2 < n; i++) {
        if (a[i] == 'A' && a[i + 1] == 'B' && a[i + 2] == 'C') {
            a[i] = 'B', a[i + 1] = 'C', a[i + 2] = 'A';
            ans++;
            i = max(-1, i - 2);
        }
    }
    */
    return ans;
}

int main(void) {
//	in = fopen("B.in", "rt");
	
	fscanf(in, "%s", a);
	n = (int)strlen(a);
	
	fprintf(out, "%lld\n", solve());
	
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    int tmpp;
    int count=0;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++)
    {
        cin >> tmpp;
        vec[i] = tmpp;
    }

    for (int i = 0; i < n-2; i++)
    {
        if ((vec[i] < vec[i + 1] && vec[i + 1] < vec[i + 2])|| (vec[i] > vec[i + 1] && vec[i + 1] > vec[i + 2]))
        {
            count++;
        }
    }

    cout << count;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <iomanip>
#define ll long long
using namespace std;
using p = pair<ll, ll>;
ll dx[4] = {1, 0, -1, 0};
ll dy[4] = {0, 1, 0, -1};

int main(void){
    ll n;
    cin >> n;
    ll ans = n*n*n;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)

abc = []
m.times do 
    a, _ = gets.split
    c = gets.split.map(&:to_i)
    abc << [a.to_i, c]
end

abc.sort_by!{|a, c| a}
r = 1 << n
dp = Array.new(r, 1 << 40)
dp[0] = 0

abc.each do |a, c|
    c = c.inject(0){|r, v| r | 1 << v - 1}
    (r - 1).downto(0) do |i|
        dp[i | c] = dp[i] + a if dp[i | c] > dp[i] + a
    end
end

puts dp[-1] == 1 << 40 ? -1 : dp[-1]

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

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 2e5 + 10;
const ll inf = 1e18L;

int n, m;
ll dp[maxN], add[maxN], res = 0;
vector <pair <int, ll>> rem[maxN];
struct node
{
    ll val, lazy;
} f[maxN * 4];
int L, R;
ll val;

void down(int x)
{
    ll t = f[x].lazy;
    f[x].lazy = 0;
    f[x * 2].lazy += t;
    f[x * 2].val += t;
    f[x * 2 + 1].lazy += t;
    f[x * 2 + 1].val += t;
}

void update(int x, int low, int high)
{
    if (high < L || low > R)
    {
        return;
    }
    if (high <= R && low >= L)
    {
        f[x].val += val;
        f[x].lazy += val;
        return;
    }
    int mid = (low + high) / 2;
    down(x);
    update(x * 2, low, mid);
    update(x * 2 + 1, mid + 1, high);
    f[x].val = max(f[x * 2].val, f[x * 2 + 1].val);
}

ll query(int x, int low, int high)
{
    if (high < L || low > R)
    {
        return -inf;
    }
    if (high <= R && low >= L)
    {
        return f[x].val;
    }
    int mid = (low + high) / 2;
    down(x);
    return max(query(x * 2, low, mid), query(x * 2 + 1, mid + 1, high));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    fill(f, f + maxN * 4, node{-inf, 0});
    while (m--)
    {
        int l, r;
        ll c;
        cin >> l >> r >> c;
        add[l] += c;
        rem[r].eb(l, c);
    }
    L = 1, R = 1, val = inf;
    update(1, 1, n);
    for1(i, n)
    {
        //Put 1 at index i
        //Add the costs of all ranges start at index i into previous index
        L = 1, R = i, val = add[i];
        update(1, 1, n);
        //Get the answer
        L = 1, R = i;
        ll best = query(1, 1, n);
        //Update current answer to segment tree
        L = i + 1, R = i + 1, val = best + inf;
        update(1, 1, n);
        uax(res, best);
        //Remove the costs of all ranges end at index i which added before
        for (auto &rn: rem[i])
        {
            L = 1;
            R = rn.fi;
            val = -rn.se;
            update(1, 1, n);
        }
    }
    cout << res;
    return 0;
}


Measured memory_bytes: 25216
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i) 
#define PI acos(-1)

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

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

    int N, K;
    cin>>N>>K;
    if (N % K == 0) cout<<0<<endl;
    else cout<<1<<endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 100005
#define NIL -1

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

Node T[MAX];
int n, D[MAX];

void print(int u){
    int i, c;
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";
    
    if(T[u].p == NIL){
        cout << "root, ";
    }else if(T[u].l == NIL){
        cout << "leaf, ";
    }else{
        cout << "internal node, ";
    }
    
    cout << "[";
    
    for(i = 0, c = T[u].l; c != NIL; ++i, c = T[c].r){
        if(i){
            cout << ", ";
        }
        cout << c;
    }
    
    cout << "]" << endl;
}

int rec(int u, int p){
    D[u] = p;
    if(T[u].r != NIL){
        rec(T[u].r, p);
    }
    if(T[u].l != NIL){
        rec(T[u].l, p+1);
    }
}

int main(){
    int i, j, d, v, c, l, r;
    cin >> n;
    for(i=0;i<n;++i){
        T[i].p=T[i].l = T[i].r = NIL;
    }
    
    for(i=0;i<n;++i){
        cin >> v >> d;
        for(j=0;j<d;++j){
            cin >> c;
            if(j==0){
                T[v].l =c;
            }else{
                T[l].r = c;
            }
            l = c;
            T[c].p=v;
        }
    }
    
    for(i=0;i<n;i++){
        if(T[i].p == NIL){
            r = i;
        }
    }
    
    rec(r,0);
    
    for(i=0;i<n;i++){
        print(i);
    }
    
    return 0;
}


Measured memory_bytes: 7764
#include<stdio.h>
#include<string.h>
int main(){
	char a[10200];
	int N;
	scanf("%d",&N);
	scanf("%s",a);
	int n,i;
	n=strlen(a);
	for(i=0;i<n;i++){
		a[i]=((a[i]-'A')+N)%26+'A';
	}
	printf("%s",a);
}

Measured memory_bytes: 128
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String s = scanner.nextLine();
            int min = 1000000;
            for (int i = 0; i <= s.length() - 3; i++) {
                String c = s.substring(i, i + 3);
                int p = Integer.parseInt(c);
                min = Math.min(Math.abs(p - 753), min);
            }
            System.out.println(min);
        }
    }
}

Measured memory_bytes: 22612
#include<stdio.h>
int main(void){
	int i, j, a, b;

	while (1)
	{
		scanf("%d %d", &a, &b);
		if (a == 0 && b == 0) 
			break;
		for (i = 0; i<a; i++)
		{
			for (j = 0; j<b; j++)
			{
				printf("#");
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}


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

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() {
  string s, t;
  cin >> s >> t;
  int ans  = 0;
  for(int i = 0; i < s.size(); ++i){
    if(s[i] == t[i]) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
	long long K=1000000000000001;
	long long N;
  	int p;
  	string s;
  	char c;

	cin >> N;
 	N--;
	s="";
	if (N==0){
		cout << "a" << endl;
      	return 0;
    }
	p=N%26;
	N=N/26;
  	c='a'+p;
	s=c+s;
	while(N>0){
      	N--;
		p=N%26;
	 	N=N/26;
  		c='a'+p;
		s=c+s;
    }
	cout << s << endl;
  	return 0;
}

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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//Write From this Line


const ll mod = 1e9+7;
ll dp[103][4][4][4];
int main()
{
	int n;
	cin >> n;

	dp[0][3][3][3] = 1;

	for(int length = 1; length <= n; length++){
		rep(i,4){ // 追加する文字の一文字前
			rep(j,4){ // 二文字前
				rep(k,4){ //3文字前
					rep(a,4){
						if(i == 1 && j == 0 && a == 2) continue;
						if(i == 2 && j == 0 && a == 1) continue;
						if(i == 0 && j == 1 && a == 2) continue;
						if(i == 1 && k == 0 && a == 2) continue;
						if(j == 1 && k == 0 && a == 2) continue;
						dp[length][a][i][j] += dp[length-1][i][j][k];
						dp[length][a][i][j] %= mod;
					}
				}
			}
		}
	}
	ll ans = 0;
	rep(i,4){
		rep(j,4){
			rep(k,4){
				ans += dp[n][i][j][k];
				ans %= mod;
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3680
#include <stdio.h>

int main(void){
	int N,K;
	scanf("%d %d",&N,&K);
	
	int A[N];
	int i;
	/*
	for(i=0;i<N;i++)
	{
		scanf("%d",&A[i]);
	}
	*/
	int ans = 1;
	N = N - K;
	K--;
	while(1){
		if(N <= 0) break;
		ans++;
		N -= K;
	}
	printf("%d",ans);
	return 0;
}
	




Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,h[100001]={},ans=0,a;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    if(a<=n)h[a]++;
  }
  for(int i=0;i<=n;i++){
    if(h[i]>=i)ans+=i;
  }
  cout<<n-ans<<endl;
  return 0;
}


Measured memory_bytes: 640
N,M=gets.split.map(&:to_i)
ans=[]
if N.odd?
  1.upto(M).each.with_index do |a,i|
    ans<<[a,M+M-i]
  end
else
  m=(M+1)/2
  1.upto(m).each.with_index do |a,i|
    ans<<[N-i,N-m-m+i]
    ans<<[a,m+m-i]
  end
  ans.shift if M.odd?
end
puts ans.map{|i|i*" "}

Measured memory_bytes: 33796
var r1 = 0, r2  =0;
(require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')[1]).split(' ').map(e => parseInt(e)).sort((a, b) => a < b ? 1 : b < a ? -1 : 0).forEach((v, i) => i % 2 == 0 ? r1 += v : r2 += v);
console.log(r1 - r2);

Measured memory_bytes: 7500
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("7 5 1");
            //YES
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 2 1");
            //NO
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 100 97");
            //YES
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("40 98 58");
            //YES
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("77 42 36");
            //NO
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int[] wkArr = InputList[0].Split(' ').Select(X => int.Parse(X)).ToArray();

        int A = wkArr[0];
        int B = wkArr[1];
        int C = wkArr[2];

        int AModB = A % B;

        var ModSet = new HashSet<int>();

        int CurrMod = A;
        CurrMod %= B;
        while (true) {
            if (ModSet.Add(CurrMod) == false)
                break;
            CurrMod += A;
            CurrMod %= B;
        }
        Console.WriteLine(ModSet.Contains(C) ? "YES" : "NO");
    }
}


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

const int maxn = 100010;
int n, a[maxn];
map<int, int> cnt;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]), cnt[a[i]]++;
    }
    sort(a + 1, a + n + 1);
    bool flag = 1;
    for (int i = 1; i <= n; i++) {
        flag &= !a[i];
    }
    if (flag) printf("Yes\n"), exit(0);
    if (n % 3) printf("No\n"), exit(0);
    if (cnt.size() == 3 && cnt[a[1]] == n / 3 && cnt[a[n]] == n / 3 && cnt[a[1] ^ a[n]] == n / 3) {
        printf("Yes\n"), exit(0);
    }
    if (cnt.size() == 2 && cnt[a[1]] == n * 2 / 3 && cnt[a[n]] == n / 3) {
        printf("Yes\n"), exit(0);
    }
    if (cnt.size() == 2 && cnt[a[1]] == n / 3 && cnt[a[n]] == n * 2 / 3) {
        printf("Yes\n"), exit(0);
    }
    printf("No\n");
    return 0;
}

Measured memory_bytes: 4224
R, G, B, N = map(int, input().split())

ans = 0
for i in range(N // R + 1):
  for j in range((N - i * R) // G + 1):
    ball = i * R + j * G
    if N == ball:
      ans += 1
    elif (N - ball) % B == 0:
      ans += 1

print(ans)

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }
template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

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

    ll N, M, K;
    cin >> N >> M >> K;
    vector<ll> A(N), B(M), sumA(N), sumB(M);
    rep(i, N) cin >> A[i];
    rep(i, M) cin >> B[i];

    sumA[0] = A[0]; sumB[0] = B[0];
    rep(i, N-1) sumA[i+1] = A[i+1] + sumA[i];
    rep(i, M-1) sumB[i+1] = B[i+1] + sumB[i];
    
    ll ans = 0;

    rep(i, N) {
      ll cnt = 0;
      if (K - sumA[i] >= 0) cnt = i + 1;
      ll amari = max(0LL, K - sumA[i]);

      ll idx = lower_bound(all(sumB), amari) - sumB.begin();
      cnt += idx;
      if (amari == sumB.back()) cnt++;

      ans = max(ans, cnt);
    }

    rep(i, M) {
      ll cnt = 0;
      if (K - sumB[i] >= 0) cnt = i + 1;
      ll amari = max(0LL, K - sumB[i]);

      ll idx = lower_bound(all(sumA), amari) - sumA.begin();
      cnt += idx;
      if (amari == sumA.back()) cnt++;

      ans = max(ans, cnt);
    }

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

Measured memory_bytes: 9536
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(input()))

cnt = 0
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            cnt += 1

x, y = 0, 0
seen = 0
while 0 <= x < W and 0 <= y < H:
    #print(x, y)
    if 0 <= y < H - 1 and A[y + 1][x] == '#':
        y = y + 1
        seen += 1
    elif 0 <= x < W - 1 and A[y][x + 1] == '#':
        x = x + 1
        seen += 1
    elif x == W - 1 and y == H - 1:
        #print(cnt)
        if seen == cnt - 1:
            print('Possible')
            break
        else:
            print('Impossible')
            break
    else:
        print('Impossible')
        break




Measured memory_bytes: 38256
#include <stdio.h>

int main(void)
{
	int H,W,a,b;
	while(1){
		scanf("%d %d",&H,&W);
		if(H==0&&W==0){
			break;
		}
		for(a=1;a<W;a++){
			printf("#");
		}
		printf("#\n");
		for(b=2;b<H;b++){
			printf("#");
			for(a=2;a<W;a++){
				printf(".");
			}
			printf("#\n");
		}
		for(a=1;a<W;a++){
			printf("#");
		}
		printf("#\n\n");
	}
	return 0;
}

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

using namespace std;

const int N=1e6+3;

#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;

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

const int inf=1e9;

int n,m,a[N],b[N],k,q,u,x,y,tc,c,l,r,ans,p,cnt;

char s[N];

bool vis[8];

vector<int> g[8];

int dfs(int u,int vis,int d){
    if (d==n)
        return 1;
	int ans=0;
	vis|=(1<<u);
	for(auto v:g[u]){
        if (((1<<v) & vis) == 0)
            ans+=dfs(v,vis,d+1);
    }
	return ans;
}

int main(){
//	#ifndef ONLINE_JUDGE
//		freopen("test.txt","r",stdin);
//	#endif
	scanf("%d%d",&n,&m);
	while(m--){
		int u,v;
		scanf("%d%d",&u,&v);
		g[--u].push_back(--v);
		g[v].push_back(u);
	}
	printf("%d",dfs(0,0,1));
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cassert>
#include <cstdint>
#include <cctype>
#include <numeric>
#include <bitset>
#include <functional>

using namespace std;

using ll =  long long;
using Pll = pair<ll, ll>;
using Pii = pair<int, int>;

constexpr ll MOD = 1000000007;
constexpr long double EPS = 1e-10;
constexpr int dyx[4][2] = {
    { 0, 1}, {-1, 0}, {0,-1}, {1, 0}
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k, p[3];
    cin >> n >> k;
    cin >> p[0] >> p[1] >> p[2];
    string s;
    cin >> s;
    vector<int> v(n);
    for(int i=0;i<n;++i) v[i] = (s[i] == 'r')?0:((s[i] == 's')?1:2);

    ll ans = 0LL;
    vector<int> hist(n, -1);
    for(int i=0;i<n;++i) {
        int j = (v[i]+2)%3;
        if(i >= k && j == hist[i-k]) {
            continue;
        } else {
            ans += p[j];
            hist[i] = j;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 1232
n = gets
arr = gets.chomp.split
arro = arr.clone
arr0 = arr.clone
arr1 = arr.clone

def bubble_sort(arr)
  count = 0
  arr.length.times do |i|
    j = arr.length - 1
    while j >= i+1
      if(arr[j-1][1] > arr[j][1])
        tmp = arr[j-1]
        arr[j-1] = arr[j]
        arr[j] = tmp
      end
      j -= 1
    end
    count += 1
  end
  puts arr.join(' ')
  puts 'Stable'
  return arr
end

def select_sort(arr)
  arr.length.times do |i|
    mini = i
    j = i
    while j < arr.length
      if(arr[j][1] < arr[mini][1])
        mini = j
      end
      j += 1
    end
    if(i != mini)
      temp = arr[i]
      arr[i] = arr[mini]
      arr[mini] = temp
    end
  end
  puts arr.join(' ')
  puts is_stable(@std, arr)
end

def is_stable(std, arr)
  arr.length.times do |i|
    return "Not stable" if(std[i] != arr[i])
  end
  return "Stable"
end

@std = bubble_sort(arr0)
select_sort(arr1)


Measured memory_bytes: 6876
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<vector<int>> ks;
  vector<int> p;
  rep(i, M) {
    int tmpk;
    vector<int> tmpVec;
    cin >> tmpk;
    
    rep(i, tmpk) {
      int tmps;
      cin >> tmps;
      tmpVec.push_back(tmps);
    }
    
    ks.push_back(tmpVec);
  }
  rep(i, M) {
    int tmpP;
    cin >> tmpP;
    p.push_back(tmpP);
  }
  
  int ans = pow(2, N);
  
  rep(i, pow(2, N)) {
    //cout << "-----test" << i << endl;
    vector<int> on;
    int tmpI = i;
    rep(s, N) {
      on.push_back(tmpI%2);
      tmpI /=2;
    }
    
    rep(j, M) {//各電球について判定
      //cout << "judge" << j << endl;

      int on_switch = 0; // on の個数
      
      rep(sk, ks[j].size()) { // Onになっているスイッチを数える
        on_switch += on[ks[j][sk]-1];
      }
      
      if(on_switch%2 != p[j]) {
        ans--;
        break; // 1つでも電球がつかない
      } else {
        //cout << "OK" << endl;
      }
    }
    
  }

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


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

using namespace std;


int main()
{
	int n;
	while (1)
	{
		cin >> n;
		if (n == 0)break;
		double he[1100];
		double heikin, goukei=0;
		for (int i = 0; i < n; i++)
		{
			cin >> he[i];
			goukei += he[i];
		}
		heikin = goukei / n;
		//cout << heikin << endl;
		double f=0;
		for (int i = 0; i < n; i++)
		{
			f += (he[i] - heikin)*(he[i] - heikin);
		}
		cout <<fixed<< sqrt(f/n) << endl;
	}
//cout << "0.0000000000" << endl;
}

Measured memory_bytes: 1292
#include <iostream>
#include <string>
#include <math.h>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main() {
    int a;
    cin>>a;
    long long int b=1;
    
    while(a!=0){
        b*=a;
        a--;
    }
    
    cout<<b<<endl;
    
    return 0;
}

Measured memory_bytes: 1156
import sys

readline = sys.stdin.readline
N = int(readline())
E = [[] for _ in range(N)]
for _ in range(N-1):
    a, b, c = map(int, readline().split())
    E[a-1].append((b-1, c))
    E[b-1].append((a-1, c))

Q, K = map(int, readline().split())
dist = [-1] * N
dist[K-1] = 0
q = [K-1]
while q:
    x = q.pop()
    d = dist[x]
    for i, j in E[x]:
        if dist[i] == -1:
            dist[i] = d + j
            q.append(i)
for _ in range(Q):
    x, y = map(int, readline().split())
    print(dist[x-1] + dist[y-1])


Measured memory_bytes: 43440
#include<stdio.h>

int main(void){
    int a,b,c;
    int i=0,cnt=0;

    scanf("%d %d %d",&a,&b,&c);
    for(i=a;i<=b;i++){
        if(c%i==0){
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}


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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<int,int> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

int main() {
    ll s;
    cin >> s;

    ll x1 = 1e9, y1;
    ll x2 = 1, y2 = ceil((double) s / x1);
    ll x3 = 0, y3 = 0;
    y1 = x1 * y2 - s;

    printf("%lld %lld %lld %lld %lld %lld\n",x1,y1,x2,y2,x3,y3);

    return 0;
}

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

#define FOR(i,a,n) for(int i = (a); i < (n); ++i)
#define REP(i,n) FOR(i,0,n)
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)

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

int N, C;
int s[100000], t[100000], c[100000];
int tt[200002];
int sm[200002];

int main() {
  cin >> N >> C;
  REP(i, N) cin >> s[i] >> t[i] >> c[i];
  REP(i, C+1) {
    REP(j,200002) tt[j] = 0;
    REP(j, N) if (c[j]==i) tt[s[j]*2-1]++, tt[t[j]*2]--;
    FOR(j,1,200002) tt[j] += tt[j-1];
    REP(j,200002) if (tt[j] > 0) sm[j]++;
  }
  int max = 0;
  REP(i,200002) chmax(max,sm[i]);
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 3576
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int D = sc.nextInt();
        int[][] X = new int[N][D];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < D; j++) {
                X[i][j] = sc.nextInt();
            }
        }
        sc.close();

        System.out.println(GoodDistance(N, D, X, 0));
    }
    public static int GoodDistance(int N, int D, int[][] X, int index) {
        if (index >= N) {
            return 0;
        }
        int ans = 0;
        for (int i = index+1; i < N; i++) {
            long sum = 0;
            for (int j = 0; j < D; j++) {
                sum += (X[index][j] - X[i][j]) * (X[index][j] - X[i][j]);
            }
            long sum2 = (long)Math.sqrt(sum);
            if (sum == sum2 * sum2) {
                ans++;
            }
        }
        return ans + GoodDistance(N, D, X, index + 1);
    }
}


Measured memory_bytes: 21844
class dice init = object (self)
  val mutable d:int*int*int*int*int*int = init

  method private tn (x1,x2,x3,x4,x5,x6):int*int*int*int*int*int = (x2,x6,x3,x4,x1,x5)
  method private ts l = self#tn l |> self#tn |> self#tn
  method private te (x1,x2,x3,x4,x5,x6):int*int*int*int*int*int = (x4,x2,x1,x6,x5,x3)
  method private tw l = self#te l |> self#te |> self#te

  method id = ()
  method north = d <- self#tn d
  method south = d <- self#ts d
  method east = d <- self#te d
  method west = d <- self#tw d
  method top = match d with (x1,_,_,_,_,_) -> x1
end;;

let split_int s = Str.split (Str.regexp_string " ") s |> List.map int_of_string;;
let n = read_line () |> split_int |> List.nth and
    s = read_line () in
    let l = (n 0,n 1,n 2,n 3,n 4,n 5) in
    let d = new dice l in
    let rec loop = function
        i when i = String.length s -> Printf.printf "%d\n" d#top
      | i -> ( match s.[i] with
               'N' -> d#north
             | 'S' -> d#south
             | 'E' -> d#east
             | 'W' -> d#west
             | _ -> d#id );
             loop (i+1)
    in loop 0;;

Measured memory_bytes: 2376
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define y0 y_0
#define y1 y_1
#define yn y_n
#include <assert.h>
#include <algorithm>
#include <vector>
using namespace std;

int n,dpa[2][20],res;
char a[20];

int main(){
	scanf("%s",&a);
	n=strlen(a);
	res=dpa[1][n-1]=a[n-1]-'0';
	dpa[0][n-1]=max(0,dpa[1][n-1]-1);
	for(int i=n-2;i>=0;i--){
		dpa[0][i]=(a[i]=='0'?0:a[i]-'0'-1+(n-i-1)*9);
		dpa[1][i]=a[i]-'0'+max(dpa[0][i+1],dpa[1][i+1]);
	}
	printf("%d\n",max(dpa[0][0],dpa[1][0]));
	return 0;
}


Measured memory_bytes: 768