akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>

std::string pattern[] = {
    "mew",
    "mCew", "meCw",
    "mCeCw"
};

std::string replaceAll(const std::string& s, const std::string& find, const std::string& to) {
    std::string::size_type pos = 0;
    std::string result = s;
    while ((pos = result.find(find, pos)) != std::string::npos) {
        result.replace(pos, find.length(), to);
        pos += to.length();
    }
    return result;
}

int main() {
    std::string s;
    std::cin >> s;
    if (s.empty()) {
        std::cout << "Cat" << std::endl;
        return 0;
    }


    while (1) {
        int isChanged = false;
        if (s == "C") {
            std::cout << "Cat" << std::endl;
            return 0;
        }
        for (int i = 0; i < s.size() - 2; i++) {
            for (auto& x : pattern) {
                if (i > s.size() - x.size()) continue;
                if (s.substr(i, x.size()) == x) {
                    s = replaceAll(s, x, "C");
                    isChanged = true;
                    break;
                }
            }
            if (isChanged) break;
        }
        if (!isChanged) break;
    }

    std::cout << "Rabbit" << std::endl;
    return 0;
}


Measured memory_bytes: 3184
N, K = map(int, input().split())
h_arr = []
for i in range(N):
    h_arr.append(int(input()))
h_arr = sorted(h_arr)
min_diff = 10**9
for i in range(N-K+1):
    diff = h_arr[i+K-1] - h_arr[i]
    if min_diff > diff:
        min_diff = diff
print(min_diff)

Measured memory_bytes: 8280
A = 3.times.inject([]) {|m, _|
  m + gets.split.map(&:to_i)
}

N = gets.to_i
c = []

N.times do
  b = gets.to_i
  index = A.index(b)
  if index
    c[index] = true
  end
end

if c[0] && c[1] && c[2]
  puts 'Yes'
elsif c[3] && c[4] && c[5]
  puts 'Yes'
elsif c[6] && c[7] && c[8]
  puts 'Yes'
elsif c[0] && c[3] && c[6]
  puts 'Yes'
elsif c[1] && c[4] && c[7]
  puts 'Yes'
elsif c[2] && c[5] && c[8]
  puts 'Yes'
elsif c[0] && c[4] && c[8]
  puts 'Yes'
elsif c[2] && c[4] && c[6]
  puts 'Yes'
else
  puts 'No'
end

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

#define rep(i,n) for(int i=0 ; i<(n) ; i++)
#define repr(i,n) for(int i=(n) ; i>=0 ; i--)
#define FOR(i,m,n) for(int i=(m) ; i<(n) ; i++)
#define FORR(i,m,n) for(int i=(m) ; i>=(n) ; i--)

#define All(x) (x).begin(),(x).end()

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

int main(){
   int n,a,b;
   cin >> n >> a >> b;
   int ans = 0;
   for(int i=0;i<=n;i++){
      int tmp = i;
      int sum = 0;
      while(tmp != 0){
         sum += tmp%10;
         tmp/=10;
      }
      if(sum >= a && sum <= b){
         ans += i;
      }
   }
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 384
/*author: hyperion_1724
  date: 
*/

//Optional FAST

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")

//Required Libraries

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

//Required namespaces

using namespace std;
using namespace __gnu_pbds;

//Required defines

#define endl '\n'

#define READ(X) cin>>X;
#define READV(X) long long X; cin>>X;
#define READAR(A,N) long long A[N]; for(long long i=0;i<N;i++) {cin>>A[i];}
#define rz(A,N) A.resize(N);
#define sz(X) (long long)(X.size())
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define trav(x,A) for(auto &x:A)
#define FORI(a,b,c) for(long long a=b;a<c;a++)
#define FORD(a,b,c) for(long long a=b;a>c;a--)

//Required typedefs

typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<long long,null_type,greater<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set1;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef vector<int> veci;
typedef vector<long long> vecl;

//Required Constants

const long long inf=(long long)1e18;
const long long MOD=(long long)(1e9+7);
const long long INIT=(long long)(1e6+1);

//Required Functions

ll power(ll x,ll y) 
{ 
	if (y == 0) 
		return 1; 
	ll p = power(x, y/2) % MOD; 
	p = (p * p) % MOD; 
  
	return (y%2 == 0)? p : (x * p) % MOD; 
}
ll modInverse(ll a) 
{ 
   return power(a,MOD-2); 
   
}

//Work

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

	READV(N);
	READV(M);
	READV(L);
	ll ans[N+1][N+1];
	FORI(i,0,N+1)
	{
		FORI(j,0,N+1)
		{
			ans[i][j]=inf;
		}
	}
	FORI(i,0,M)
	{
		READV(a);
		READV(b);
		READV(c);
		ans[a][b]=min(ans[a][b],c);
		ans[b][a]=min(ans[b][a],c);
	}
	FORI(k,1,N+1)
	{
		FORI(i,1,N+1)
		{
			FORI(j,1,N+1)
			{
				ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);
				ans[j][i]=ans[i][j];
			}
		}
	}
	FORI(i,0,N+1)
	{
		FORI(j,0,N+1)
		{
			if(ans[i][j]<=L)
			{
				ans[i][j]=1;
			}
			else
			{
				ans[i][j]=inf;
			}
		}
	}
	FORI(k,1,N+1)
	{
		FORI(i,1,N+1)
		{
			FORI(j,1,N+1)
			{
				ans[i][j]=min(ans[i][j],ans[i][k]+ans[k][j]);
				ans[j][i]=ans[i][j];
			}
		}
	}
	READV(T);
	while(T--)
	{
		READV(a);
		READV(b);
		if(ans[a][b]<inf)
		{
			cout<<ans[a][b]-1<<endl;
		}
		else
		{
			cout<<-1<<endl;
		}
	}

	return 0;
}

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

using namespace std;

#define abs(a, b) ((a < b) ? b - a : a - b)

const int N_max = 100000;
int N;
int A[N_max + 2];

int main(){
    
    A[0] = 0;

    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> A[i];
    
    A[N + 1] = 0;

    int B[N + 1];
    int sum = 0;
    for(int i = 0; i < N + 1; i++){
        B[i] = abs(A[i], A[i + 1]);
        sum += B[i];
    }

    int C[N];
    for(int i = 0;i < N; i++)
        C[i] = abs(A[i], A[i + 2]);

    for(int i = 0; i < N; i++){
        int temp = sum;
        temp += C[i];
        temp -= B[i] + B[i + 1];

        cout << temp << '\n';
    }

    return 0;

}



Measured memory_bytes: 2432
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DEBUG
#ifdef DEBUG
#define debug(...) __f(#__VA_ARGS__, __VA_ARGS__)
	template <typename Arg1>
	void __f(const char* name, Arg1&& arg1)
	{
		cerr << name << " = " << arg1 << endl;
	}
	template <typename Arg1, typename... Args>
	void __f(const char* names, Arg1&& arg1, Args&&... args)
	{
		const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " = " << arg1 << " || ";
		__f(comma+1, args...);
	}
#else
#define debug(...)
#endif

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ; ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

#define FAST_IO std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"

// priority_queue<ll, vector<ll>, less<ll>>pq;     // Max Heap
// priority_queue<ll, vector<ll>, greater<ll>>pq;  // Min Heap

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth (1 based indexing) smallest: " << *A.find_by_order(k - 1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

const int MAXN = 2e5 + 5;

ll dp[MAXN], n, k, a[MAXN], nx[MAXN], prevv[MAXN], cnt[MAXN], fst[MAXN];

ll rec(ll ind)
{
	if(ind >= n) return n;
	if(dp[ind] != -1) return dp[ind];
	if(nx[ind] == n) return dp[ind] = ind;
	return dp[ind] = rec(nx[ind] + 1);
}

int main()
{
	FAST_IO;

 	cin >> n >> k;
 	memset(prevv, -1, sizeof(prevv));
 	memset(fst, -1, sizeof(fst));
 	for(int i=0;i<n;i++) cin >> a[i];
 	for(int i=0;i<n;i++)
 		if(fst[a[i]] == -1) fst[a[i]] = i;
 	for(int i=n-1;i>=0;i--)
 	{
 		if(prevv[a[i]] == -1) nx[i] = n;
 		else nx[i] = prevv[a[i]];	
 		prevv[a[i]] = i;
 	}
 	memset(dp, -1, sizeof(dp));
 	vector<ll>val, ans;
 	ll curr = 0;
 	while(1)
 	{
 		curr = rec(curr);
 		val.pb(curr);
 		if(curr == n) break;
 		curr = fst[a[curr]] + 1;
 	}
 	ll w = (k - 1) % sz(val);
 	for(int i=val[w];i<n;i++)
 	{
 		if(cnt[a[i]] == 0) ans.pb(a[i]), cnt[a[i]] += 1;
 		else
 		{
 			while(1)
 			{
 				ll x = ans.back();
 				cnt[x] -= 1;
 				ans.pop_back();
 				if(x == a[i]) break;
 			}
 		}
 	}
 	for(auto it : ans) cout << it << " ";
 	cout << endl;
    return 0;
}

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

#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define all(a)      (a).begin(),(a).end()
#define x           first
#define y           second
#define sz(x)       (int)x.size()
#define endl        '\n'
#define hell        1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
using namespace std;

int main(){
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	//insert code
	int n,k;
	cin>>n>>k;
	vi arr(n);
	rep(i,0,n)cin>>arr[i];
	vector<bool>dp(k+1);
	for (int i=0;i<=k;i++){
		for (int p:arr){
			if (i>=p && !dp[i-p])dp[i]=true;
		}
	}
	if (dp[k])cout<<"First"<<endl;
	else cout<<"Second"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
void Say(bool say, string a = "Yes", string b = "No"){cout << (say ? a : b) << endl;};

int main(){

    ll N;
    cin >> N;
    ll ans = 0;
    vector<ll>v(N + 1, 0);
    vector<ll>r(N + 1, 0);
    for(ll i = 1; i <= N; i++)cin >> v[i];
    for(ll i = 1, j = 0; i < N; i++){
        if(v[i] >= v[i + 1]){
            j++;
            ans = max(ans, j);
        }
        else j = 0;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

int dfs(int * a,int& n,int lastNumber,int maxNumber,int currentLength,int lastIndex);
int main(){
	int n;
	cin>>n;
	int* a=new int[n];
	memset(a,0,sizeof(int)*n);
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	int *length=new int[n+1];
	memset(length,0,sizeof(int)*(n+1));
	int maxLength=0;
	for(int i=0;i<n;i++){
		if(length[a[i]-1]==0){
			length[a[i]]=1;
		}else{
			length[a[i]]=length[a[i]-1]+1;
		}
	}
	for(int i=0;i<n;i++){
		maxLength=max(maxLength,length[i+1]);
	}
	cout<<n-maxLength<<endl;
	return 0;
}
				





Measured memory_bytes: 1792
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	ll n = in(), a = in(), b = in();
	cout << (a > b ? 0 : max((b - a) * (n - 2) + 1, 0LL)) << endl;
}

Measured memory_bytes: 256
import fractions
from functools import reduce
 
def lcm_b(a, b):
        #print("base",a,b)
        return (a * b) // fractions.gcd(a, b)
 
def lcm_o():
        global n
        return reduce(lcm_b, n)
 
def chk(v):
        global n
        for i in range(1,30):
                if v%2 == 1:break
                v = v//2
        t=2**(i-1)
        for j in range(len(n)):
                s=int(n[j]/t)
                if n[j] % t == 0 and s % 2 == 1:
                        n[j] = s
 
                else: return 0
        return int(t//2)
 
def mp(v):
        if v%2==1:v+=1
        return int(v//2)
 
N,M= [int(i) for i in input().split()]
n = [int(i) for i in input().split()]
n=sorted(set(n),reverse = True)
bs = n[0]//2
 
if len(n) > 1:
        c = chk(n[-1])
        if  c != 0:
                v = lcm_o()*c
                if v > M: print(0) 
 
                else:
                        print(mp(M//v))
                        #v = M//v
                        #if v%2==1: v+=1
                        #print(int(v//2))
        
        else: print(0)
        
elif len(n)==1:
        print(mp(M//bs))
        #v = M//bs
        #if v%2==1: v+=1
        #print(int(v//2))

Measured memory_bytes: 16308
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)(1e18)

struct BLU{
	int b;
	int l;
	int u;
};

int X;

int OtoX(BLU v){
	return v.l * v.b + v.u * (X - v.b);
}

auto compair(BLU a, BLU b){
	return OtoX(a) > OtoX(b);
}

int time(BLU v, int a){
	if(a < 0 || OtoX(v) < a){
		return inf;
	}
	int b = v.b, l = v.l, u = v.u;
	if(a <= l * b){
		return (a + l - 1) / l;
	}
	else{
		return b + (a - l * b + u - 1) / u;
	}
}

signed main(){
	int N, i, j, ini = 0;
	scanf("%lld%lld", &N, &X);
	vector<BLU> blu(N + 1);
	for(i = 1; i <= N; i++){
		scanf("%lld%lld%lld", &blu[i].b, &blu[i].l, &blu[i].u);
		ini += blu[i].l * blu[i].b;
	}
	sort(blu.begin() + 1, blu.end(), compair);
	vector<int> sum(N + 1, 0);
	for(i = 1; i <= N; i++){
		sum[i] = sum[i - 1] + OtoX(blu[i]);
	}
/*	printf("ini = %lld\n", ini);
	for(i = 0; i <= N; i++){
		printf("sum[%lld] = %lld\n", i, sum[i]);
	}
*/	int ans = inf;
	for(i = 1; i <= N; i++){
//		printf("i = %lld\n", i);
		j = lower_bound(sum.begin(), sum.end(), ini - OtoX(blu[i])) - sum.begin();
//		printf("j1 = %lld\n", j);
		if(j < i){
			ans = min(ans, X * j + time(blu[i], ini - sum[j]));
//			printf("ans1 = %lld\n", ans);
		}
		j = lower_bound(sum.begin(), sum.end(), ini) - sum.begin();
//		printf("j2 = %lld\n", j);
		if(j >= i){
			ans = min(ans, X * (j - 1) + time(blu[i], ini - sum[j] + OtoX(blu[i])));
//			printf("ans2 = %lld\n", ans);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3456
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

const int N=1e5+5,Mo=1e9+7;

int n,sum[N],f[N],nxt[N][3];
char s[N];

void inc(int &x,int y) {x=x+y>=Mo?x+y-Mo:x+y;}

int main() {
	scanf("%s",s+1);n=strlen(s+1);
	bool ok=0;
	fo(i,1,n-1) if (s[i]==s[i+1]) {ok=1;break;}
	if (!ok) {puts("1");return 0;}
	sum[0]=0;fo(i,1,n) sum[i]=(sum[i-1]+((s[i]=='a')?1:2))%3;
	fo(i,0,2) nxt[n][i]=n+1;
	fd(i,n-1,0) {
		fo(j,0,2) nxt[i][j]=nxt[i+1][j];
		nxt[i][sum[i+1]]=i+1;
	}
	f[0]=1;int ans=0;
	fo(i,0,n) {
		fo(j,1,2) inc(f[nxt[i][(sum[i]+j)%3]],f[i]);
		if (i&&sum[i]==sum[n]) inc(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 2176
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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 pair<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


signed main() {
	int X;
	cin >> X;
	if (X >= 30)cout << "Yes";
	else cout << "No";
}

Measured memory_bytes: 3632
<?php
//error_reporting(0);
$N = trim(fgets(STDIN));
//list($N,$K) = explode(" ",trim(fgets(STDIN)));
//$a = explode(" ",trim(fgets(STDIN)));
//$H = explode(" ",trim(fgets(STDIN)));
printf("%d\n",substr_count($N,"2"));


Measured memory_bytes: 3828
#include <stdio.h>
#include <iostream>
using namespace std;

int main(){
    int N,A,max=32;
    cin >> N;
    for(;N>0;N--){
        cin >> A;
        int div = 0;
        while(A%2==0){
            A /= 2;
            div ++;
        }
        if(max>div) max = div;
    }
    cout << max ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mkp make_pair
#define f(i,l,h) for(ll i=l;i<h;i++)
#define fr(i,h,l) for(ll i=h;i>=l;i--)

using namespace std;

typedef pair<ll,ll> pll;
const ll INF=(ll)(1e9+7);
typedef vector<ll> vll;



int main()
{
    //cout << "Hello world!" << endl;

    ll n;
    cin>>n;
    long double a[n];
    bool flag =false;
    f(i,0,n){
        cin>>a[i];
        if(a[i]==0){
            flag=true;
        }
    }
    if(flag){
        cout<<"0"<<endl;
        return 0;
    }

    long double prod=1;
    f(i,0,n){
        if(a[i]>(long double)(1e18)/prod){
            prod=-1;
            break;
        }
      	prod*=a[i];
    }
    cout<<(ll)prod<<endl;

}


Measured memory_bytes: 5264
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define rev(v) reverse(v.begin(), v.end())
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
#define uniq(a) sort(all(a));(a).resize(unique(all(a)) - a.begin());
#define dab(v) for(auto i:v)cout<<i<<' '; cout << endl;
#define vin(v) for (ll i = 0; i < v.size(); ++i) cin >> v[i];
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    
    int K,N; cin >>K>>N; vl A(N); rep(i,N) cin >> A[i];
	ll now = K + A[0] - A[N-1];
	rep(i,N-1) {
		ll tmp = A[i+1] - A[i];
		chmax(now,tmp);
	}
	cout << K - now << endl;
}

Measured memory_bytes: 1792
#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>;

int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    vector<ll> r;
    set<ll> s;
    r.push_back(x);
    s.insert(x);
    for (ll i = 1; i <= n; ++i) {
        x *= x;
        x %= m;
        if (s.count(x)) {
            break;
        }
        r.push_back(x);
        s.insert(x);
    }

    int len = r.size();
    int start = 0;
    rep(i, len) if (r.at(i) == x) start = i;
    ll sum = 0, ans = 0;

    rep(i, len) sum += r.at(i);

    rep(i, start) {
        sum -= r.at(i);
        ans += r.at(i);
    }
    n -= start;
    len -= start;
    ans += sum * ((ll) n / len);
    rep(i, n % len) ans += r.at(start + i);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5944
n=int(input())
cnt=[10000]*26
for i in range(n):
    tmp=[0]*26
    S=input()
    for j in range(len(S)):
        tmp[ord(S[j])-97]+=1
    for j in range(26):
        cnt[j]=min(tmp[j],cnt[j])
li=[]
for i in range(26):
    for j in range(cnt[i]):
        li.append(chr(i+97))
print(''.join(li))

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x)    // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    string s, t;
    cin >> s >> t;
    ll ans = LLONG_MAX;

    for (ll i = 0; i <= s.size() - t.size(); i++)
    {
        ll temp = 0;
        for (ll k = 0; k < t.size(); k++)
        {
            if (t[k] != s[i + k])
            {
                temp++;
            }
        }
        ans = min(ans, temp);
    }

    cout << ans << endl;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define mp make_pair
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define eb emplace_back
 
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< pii > vpii;
typedef vector< vpii > vvpii;
typedef vector< pll > vpll;
typedef long double ld;
typedef vector< ld > vld;
typedef unsigned int uint;
 
template <uint MD> struct ModInt {
    using M = ModInt;
    const static M G;
    uint v;
    ModInt(ll _v = 0) { set_v(uint(_v % MD + MD)); }
    M& set_v(uint _v) {
        v = (_v < MD) ? _v : _v - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(uint(ull(v) * r.v % MD)); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    const bool operator<(const M& o) const {return v < o.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
 
using Mint = ModInt<(int)1e9 + 7>;


int main() { 
    #ifdef BLAT
        freopen("stdin", "r", stdin);
        freopen("stderr", "w", stderr);
    #endif

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin >> s;

    cout << s.substr(0, 3) << '\n';
    return 0; 
}

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

#define ll long long

void swap (int *x, int *y) {
  int temp;

  temp = *x;
  *x = *y;
  *y = temp;

  return;
}


//naosu
long int gcd(long int a,long int b){
  long int c;

  while (b > 0){
    c = a % b;
    a = b;
    b = c;
  }

  return a;
}

int upll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;
}

int downll(const void*a, const void*b){
  return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;
}

void sortup(ll*a,int n){
  qsort(a,n,sizeof(ll),upll);
}

void sortdown(ll*a,int n){
  qsort(a,n,sizeof(ll),downll);
}

long int modpow(long int a,long int n,long int mod){
  long int ans=1;
  while(n>0){
    if(n & 1){
      ans=ans*a%mod;
    }
    a=a*a%mod;
    n/=2;
  }
  return ans;
}

long int modinv(long int a,long int mod){
  return modpow(a,mod-2,mod);
}

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

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

void chmax(int *a,int b){
  if(*a < b){
    *a = b;
  }

  return;
}

void chmin(int *a,int b){
  if(*a > b){
    *a =b;
  }

  return;
}


long int lcm(long int a,long int b){
  return a/gcd(a,b)*b;
}


long int f(long int n,long int c,long int d){
  long int cnt=n/c+n/d-n/lcm(c,d);
  return n-cnt;
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/

int main(void){
  int MOD=1e9+7; 
  /*
  long int kai[2000000];
  long int rekai[2000000];
  
  kai[0]=1;
  kai[1]=1;
  rekai[0]=1;
  rekai[1]=1;
  for(int i=2;i<2000000;i++){
    kai[i]=kai[i-1]*i;
    kai[i]%=MOD;

    rekai[i]=rekai[i-1]*modinv(i,MOD);
    rekai[i]%=MOD;
  }
  */

  long int n,p;
  scanf("%ld%ld",&n,&p);

  long int e=0;
  long int o=0;
  for(int i=0;i<n;i++){
    int a;
    scanf("%d",&a);

    if(a%2==0){
      e++;
    }
    else{
      o++;
    }
  }

  long int ans=1;
  while(e--){
    ans*=2;
  }

  //
  long int all=0;
  if(p==0){
    //oCiのiの部分を全探索
    for(long int i=0;i<=o;i+=2){
      long int res=1;
      for(long int j=o;j>o-i;j--){
        res*=j;
        res/=(o-j+1);
      }
      all+=res;
    }
  }
  else{
    for(long int i=1;i<=o;i+=2){
      long int res=1;
      for(long int j=o;j>o-i;j--){
        res*=j;
        res/=(o-j+1);
      }
      all+=res;
    }
  }

  printf("%ld\n",all*ans);

  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

#define isNum(a) (a >= '0' && a <= '9')
#define SP putchar(' ')
#define EL putchar('\n')
#define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)

template<class T>
inline void read(T&);
template<class T>
inline void write(const T&);

typedef long long ll;
typedef const long long & cll;
typedef const int & ci;
typedef std::pair<int, int> pii;
const int iinf = 2147483647;
const ll llinf = 9223372036854775807ll;
using std::min;
using std::max;
using std::abs;
using std::sort;
const int N = 205;
const int M = 100005;
const int Mod = 1000000007;

int a[N];
int dp[N][M];

int main () {
    int n, x;
    read(n), read(x);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    sort(a + 1, a + n + 1, std::greater<int>());
    dp[0][x] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < M; ++j) {
            dp[i][j % a[i]] = (dp[i][j % a[i]] + dp[i - 1][j]) % Mod;
            dp[i][j] = (dp[i][j] + dp[i - 1][j] * 1ll * (n - i) % Mod) % Mod;
        }
    }
    int ans = 0;
    for (int i = 0; i < M; ++i) {
        ans = (ans + i * 1ll * dp[n][i] % Mod) % Mod;
    }
    write(ans), EL;
    return 0;
}

template<class T>
void read(T &Re) {
    T k = 0;
    char ch = getchar();
    int flag = 1;
    while (!isNum(ch)) {
        if (ch == '-') {
            flag = -1;
        }
        ch = getchar();
    }
    while (isNum(ch)) {
        k = (k << 1) + (k << 3) + ch - '0';
        ch = getchar();
    }
    Re = flag * k;
}
template<class T>
void write(const T &Wr) {
    if (Wr < 0) {
        putchar('-');
        write(-Wr);
    } else {
        if (Wr < 10) {
            putchar(Wr + '0');
        } else {
            write(Wr / 10);
            putchar((Wr % 10) + '0');
        }
    }
}


Measured memory_bytes: 79744
d = list(map(int, input().split()))
a = list(map(int, input().split()))

n = d[0]
m = d[1]
x = d[2]

costl  = 0
costh  = 0
for i in range(m):
    if a[i] < x:
        costl += 1
    elif x < a[i]:
        costh += 1
    else:
        costl += 0

print(min(costl,costh))

Measured memory_bytes: 3064
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>

using namespace std;

int main(){
    int a,b,c;

    cin >> a >> b >> c;

    if (a < b && b < c){
        printf("Yes\n");
    }
    else printf("No\n");

    return 0;
}


Measured memory_bytes: 3080
#include<iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
const long long int mod1=1000000007;
const long long int mod2 = -1;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define pp pop_back                                       
#define ff first
#define ss second
#define ll long long int
#define ull unsigned long long int
#define ordered_set tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define ordered1 tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define inf mod1
#define all(x) x.begin(),x.end()
ll gcd(ll a, ll b){
    ll c;
     while(b){
        c = b;
        b = a % b;
        a = c;
     }
     return a;
}
ll power1(ll a, ll b){
     if(b == 0) return 1;
     else if(b % 2) return a * power1(a, b - 1);
     else {
        ll temp = power1(a, b / 2);
        return temp * temp;
     }
}
ll power2(ll a, ll b, ll m){
     a %= m;
     if(b == 0) return 1;
     else if(b % 2) return (a * power2(a, b - 1, m)) % m;
     else{
        ll temp = power2(a, b / 2, m);
        return (temp * temp) % m;
     }
}
ll mod(ll x, ll p){
return (x % p + p) % p;
}
ll lcm(ll x, ll y){
return (x * y)/gcd(x, y);
}
int main(){
    fast;
    ll h = 1;
    //scanf("%lld", &h);
    while(h--){
        string s;
        cin >> s;
        if(s[0] == '7' || s[1] == '7' || s[2] == '7'){
            cout << "Yes" << endl;
        }
        else{
            cout << "No" << endl;
        }
}
}

Measured memory_bytes: 3656
#!/usr/bin/env python3

N, K = map(int, input().split())
A = [int(a) - 1 for a in input().split()]

if K <= N:
    p = 0
    for _ in range(K):
        p = A[p]
    print(p + 1)
    exit()

p = 0
t = [-1] * N
t[0] = 0
for i in range(1, N):
    p = A[p]
    if t[p] != -1:
        break
    t[p] = i

d = i - t[p]
K -= i
K %= d

for i in range(K):
    p = A[p]
print(p + 1)

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

#define INF 1e09
#define min(a,b) (a<b?a:b)

using namespace std;

vector<int> l;
int n,a,b,c;

int func(int i,int aa,int bb,int cc){
    int res;
    if(i==n){
        if(!aa||!bb||!cc)return INF;
        else return abs(a-aa)+abs(b-bb)+abs(c-cc)-30;
    }
    res = func(i+1,aa,bb,cc);
    res = min(res,func(i+1,aa+l[i],bb,cc)+10);
    res = min(res,func(i+1,aa,bb+l[i],cc)+10);
    res = min(res,func(i+1,aa,bb,cc+l[i])+10);
    return res;
}

int main(){
    cin >> n >> a >> b >> c;
    for(int i=0;i<n;++i){
        int k;
        cin >> k;
        l.push_back(k);
    }
    cout << func(0,0,0,0) << endl;
}


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

int main() {
	string s;
	cin >> s;
	int counter = 0;
	if (s[0] == '1')++counter;
	if (s[1] == '1')++counter;
	if (s[2] == '1')++counter;
	cout << counter << endl;
	return 0;
}

Measured memory_bytes: 256
/*
  Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define mkpr make_pair
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define fbo find_by_order
#define ook order_of_key
#define init0(x) memset(x,0,sizeof(x));

using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const int maxlimit=2e5+2;
const ll inf=1e18;
//TTBDC

int main()
{
  fatafat
  int n,k;
  cin>>n>>k;
  int arr[n+1];
  for(int i=1;i<=n;i++)cin>>arr[i];
  bool dp[k+1];
  memset(dp,false,sizeof(dp));
  for(int i=1;i<=k;i++){
    for(int j=1;j<=n;j++){
      dp[i]|=i-arr[j]>=0?!dp[i-arr[j]]:0;
    }
  }
  if(dp[k])cout<<"First";
  else cout<<"Second";
  return 0;
}

Measured memory_bytes: 3716
# -*- coding: utf-8 -*-
"""
Created on Tue May 12 14:10:07 2020

@author: shinba
"""
import itertools

n,d = map(int,input().split())

X = []

for i in range(n):
    X.append(list(map(int,input().split())))

ans = 0

for i in itertools.combinations(range(n), 2):
    dist = 0
    for j in range(d):
        dist += (X[i[0]][j]-X[i[1]][j])**2
    else:
        if dist**(0.5) == int(dist**(0.5)):
            ans += 1

print(ans)


Measured memory_bytes: 3188
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  vector<int> vi;
typedef  pair<int,int> pii;
typedef  pair<int,string> pis;
double   pi=3.1415926535898;
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define lp(i,n)   for(int i=0;i<int(n);i++)
#define ff(i,a,b)  for(int i=a;i<=int(b);++i)
#define rng(i,a,b) for(int i=a;i>=int(b);i--)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define r0         return 0;
#define CC         continue;
#define bb(x)      cerr<< x <<endl;
#define F          first
#define S          second       //  __builtin_popcount;
//freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
const ll M  = 1e9+7 ;
//const int N = 111;
const int inf = 2e9+7;
const double EPS = 1e-9;
//////////////////////    Hi    ^_^  hack me if you can :P
string ys = "YES\n";
string no = "NO\n" ;


int main()
{
    int n;
    int a;
    int z=0,x=0,y=0;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a;
        if(a%4==0)
        {
            z++;
        }
        else if(a%2==0)
        {
            y++;
        }
        else
        {
            x++;
        }
    }
    if((y==0&&x<=z+1)||(y!=0&&x<=z))
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}

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

using namespace std;

int main() {
	string com;
	string str;
	string str_p;
	string str_temp;
	int n;
	int a,b;
	cin >> str;
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> com;
		if(com=="print") {
			cin >> a >> b;
			cout << str.substr(a,b-a+1) << endl;
		} else if(com=="reverse") {
			cin >> a >> b;
			str_temp=str.substr(a,b-a+1);
			str_p="";
			for(int i=0; i<b-a+1; ++i) {
				str_p+=str_temp[b-a-i];
			}
			str.replace(a,b-a+1,str_p);
		} else if(com=="replace") {
			cin >> a >> b >> str_p;
			str.replace(a,b-a+1,str_p);
		}
	}
}

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

int main(){
    int N;  cin >> N;
    vector<ll> A(N+1,0);
    for(int i=1; i<=N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    ll sum = 0;
    int ans = 0;
    for(int i=1; i<=N; i++){
        if(2*sum < A[i]){
            ans = 1;
        }else{
            ans++;
        }
        sum += A[i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner scan=new Scanner(System.in);
        int A=scan.nextInt();
        int B=scan.nextInt();
        if(A==1){
            A+=13;
        }
        if(B==1){
            B+=13;
        }
        if(A>B){
            System.out.println("Alice");
        }
        else if(A<B){
            System.out.println("Bob");
        }
        else{
            System.out.println("Draw");
        }
    }
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    cout<<fixed;
//    cout<<setprecision(10);
    ll n;
    cin>>n;
    ll a[n+5];
    for (int i=0;i<n;i++) cin>>a[i];
    bool chk=true;
    for (int i=0;i<n;i++)
    {
        if (a[i]%2) continue;
        else
        {
            if (a[i]%3==0 || a[i]%5==0)
            {
                continue;
            }
            else
            {
                chk=false;
                break;
            }
        }
    }
    if (chk) cout<<"APPROVED"<<endl;
    else cout<<"DENIED"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<string,ll>mp;
ll n,ans;
string s;
int main(void){
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    for(auto x:mp){
        ans+=x.second*(x.second-1)/2;
        }
    cout<<ans<<endl;
}


Measured memory_bytes: 11136
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <set>
#include <stack>
#include <climits>
#include <cmath>

#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(int i=1, i##_len=(n); i<=i##_len; ++i)
#define reps(i,s,n) for(int i=s, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define MEMSET(v, h) memset((v), h, sizeof(v))
typedef long long ll;
const char sp = ' ';


using namespace std;

int main(void){
    ll N, A, B;
    cin>>N>>A>>B;
    ll set=N/(A+B);
    ll sur=min(A, N-set*(A+B));
    cout<<set*A+sur<<endl;
    return 0;
}


Measured memory_bytes: 256
use std::collections::HashSet;

use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        m: usize,
        h: [usize; n],
        ab: [[Usize1; 2]; m],
    }

    let mut good_obs: HashSet<usize> = (0..n).collect();
    for xy in ab {
        let x = xy[0];
        let y = xy[1];

        if h[x] <= h[y] {
            good_obs.remove(&x);
        }

        if h[y] <= h[x] {
            good_obs.remove(&y);
        }
    }

    println!("{}", good_obs.len())
}


Measured memory_bytes: 11492
B=C=0,A=1,i=require("fs").readFileSync("/dev/stdin","utf8").split(/\n|,/);for(j=0;j<i.length-1;)eval('t='+i[j]+','+i[j++]+'='+i[j]+','+i[j++]+'=t');console.log(A?'A':B?'B':'C');

Measured memory_bytes: 7644
import math

s_num, c_num = map(int, input().split())

if c_num <= 2 * s_num:
    # Sを使い切る前にCを使い切る
    scc_num = math.floor(c_num / 2)
    print(scc_num)
else:
    # Sを使い切り、余ったCでSを作りつつSCCを作る
    scc_num = math.floor(s_num + ((c_num - 2 * s_num) / 4))
    print(scc_num)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int bingo[3][3];
bool flag[3][3];
int cnt[2][105];
int h, w;
int choco[1010][1010];
int s[11][11];

int main() {
	int n, k, r, s, p;
	cin >> n >> k >> r >> s >> p;
	string t;
	cin >> t;
	string t2;
	ll ans = 0;
	rep(i, k) {
		if (t[i] == 'r') {
			ans += p;
			t2 += "p";
		}
		else if (t[i] == 's') {
			ans += r;
			t2 += "r";
		}
		else {
			ans += s;
			t2 += "s";
		}
	}
	for (int i = k;i < n;++i) {
		if (t[i] == 'r'&&t2[i-k]!='p') {
			ans += p;
			t2 += "p";
		}
		else if (t[i] == 'r' && t2[i - k] == 'p') {
			t2 += t[i + k];
		}
		else if (t[i] == 's'&&t2[i-k]!='r') {
			ans += r;
			t2 += "r";
		}
		else if (t[i] == 's' && t2[i - k] == 'r') {
			t2 += t[i + k];
		}
		else if (t[i] == 'p' && t2[i - k] != 's') {
			ans += s;
			t2 += "s";
		}
		else if (t[i] == 'p' && t2[i - k] == 's') {
			t2 += t[i + k];
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Numerics;

//using static System.Console;

class _Class
{

  void _Do()
  {
		var s = Split.strings();
		var arr = Split.ints();
		//Array.Sort(i);
		var N = arr.Length;

		var arr2 = new int[100005];
		for (int a = 0; a < N; a++)
		{
			arr2[arr[a]]+=1;
			arr2[arr[a]+1]+=1;
			arr2[arr[a]+2]+=1;
		}
		Array.Sort(arr2);
		Array.Reverse(arr2);

		//
		Console.WriteLine(arr2[0]);
 
  }
  
	static void Main(string[] args)
	{
		new _Class()._Do();
	}

}

//
static class Split
{
	// 1
	public static string[] strings()
	{
		return Console.ReadLine().Split();
	}

  // [2.1] -2,147,483,648 ~ +2,147,483,647
  public static int[] ints()
	{
		var _s = Console.ReadLine().Split();

		var x = new int[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = int.Parse(_s[i]);

		return x;
	}

	// [2.2] 
	// -9,223,372,036,854,775,808 ~ 
	// +9,223,372,036,854,775,807
	public static long[] longs()
	{
		var _s = Console.ReadLine().Split();

		var x = new long[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = long.Parse(_s[i]);

		return x;
	}

	public static BigInteger[] bigs()
	{
		var _s = Console.ReadLine().Split();

		var x = new BigInteger[_s.Length];
		for (var i = 0; i < _s.Length; i++)
			x[i] = BigInteger.Parse(_s[i]);

		return x;
	}
}

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

int main(){
  string s,t;
  cin >> s >> t;
  sort(s.begin(),s.end());
  sort(t.begin(),t.end());
  reverse(t.begin(),t.end());

  if(s<t) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef int sign;
typedef long long ll;
#define For(i,a,b) for(register sign i=(sign)a;i<=(sign)b;++i)
#define Fordown(i,a,b) for(register sign i=(sign)a;i>=(sign)b;--i)
const int N=100+5,M=1e7;
template<typename T>bool cmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool cmin(T &a,T b){return (a>b)?a=b,1:0;}
template<typename T>T read()
{
	T ans=0,f=1;
	char ch=getchar();
	while(!isdigit(ch)&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch-'0'),ch=getchar();
	return ans*f;
}
template<typename T>void write(T x,char y)
{
	if(x==0)
	{
		putchar('0'),putchar(y);
		return;
	}
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	static char wr[20];
	int top=0;
	for(;x;x/=10)wr[++top]=x%10+'0';
	while(top)putchar(wr[top--]);
	putchar(y);
}
void file()
{
#ifndef ONLINE_JUDGE
	freopen("magic.in","r",stdin);
	freopen("magic.out","w",stdout);
#endif
}
int n,p[N];
int l[M+5],vis[M+5];
void input()
{
	n=read<int>();
	For(i,1,n)p[i]=read<int>();
	//sort(p+1,p+n+1);
//	n=unique(p+1,p+n+1)-p-1;
}
void init()
{
	For(i,2,M)
	{
		if(!vis[i])l[++l[0]]=i;
		for(int j=1;j<=l[0]&&i*l[j]<=M;++j)
		{
			vis[i*l[j]]=1;
			if(i%l[j]==0)break;
		}
	}
	vis[1]=1;
}

int pos[N<<1],top;
vector<int>E[2];
#define pb push_back
int match[N<<1],leg[N<<1];
int mp[N<<1][N<<1];
bool dfs(int u,int id)
{
	int v;
	For(i,0,E[(!(pos[u]&1))].size()-1)
	{
		v=E[(!(pos[u]&1))][i];
		if(leg[v]^id&&!vis[abs(pos[u]-pos[v])])
		{
			//cerr<<u<<' '<<v<<endl;  
			leg[v]=id;
			if(!match[v]||dfs(match[v],id))
			{
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}
void work()
{
	int r;
	For(i,1,n)
	{
		r=i;
		while(r<n&&p[r+1]==p[r]+1)r++;
		pos[++top]=p[i];
		pos[++top]=p[r]+1;
		i=r;
	}
	int ans=0;
	//For(i,1,top)cout<<pos[i]<<endl;
	For(i,1,top)E[(pos[i]&1)].pb(i);
	int res0=0,res1=0;
	For(i,1,top)
	{
		if(pos[i]&1)
		{
			if(dfs(i,i))ans++;
			res1++;
		}
		else res0++;
	}
//	For(i,1,top)cout<<match[i]<<endl;
	//cerr<<ans<<endl;
//	For(i,1,top)cout<<vis[abs(pos[i]-pos[match[i]])]<<' '<<abs(pos[i]-pos[match[i]])<<endl;
	res1-=ans,res0-=ans;
	ans+=(res0/2)*2+(res1/2)*2;
	res0%=2,res1%=2;
	if(res0&&res1)ans+=3;
	write(ans,'\n');
}
int main()
{
	//file();
	input();
	init();
	work();
	return 0;
}

Measured memory_bytes: 43136
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.NoSuchElementException;

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
        return (int) nl;
    }
    public double nextDouble() { return Double.parseDouble(next());}
}

class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	
	void run() {
		FastScanner sc = new FastScanner();
		int H=sc.nextInt();
		int W=sc.nextInt();
		int K=sc.nextInt();
		int[] h=new int[K];
		int[] w=new int[K];
		long[][][] dp=new long[4][H+1][W+1];
		long[][] v=new long[H+1][W+1];
		for (int i=0;i<K;++i) {
			h[i]=sc.nextInt();
			w[i]=sc.nextInt();
			v[h[i]][w[i]]=sc.nextLong();
		}
		long ans=0;
		for (int y=1;y<=H;++y) {
			for (int x=1;x<=W;++x) {
				for (int sum=1;sum<=3;++sum) {
					dp[sum][y][x]=Math.max(dp[3][y-1][x]+v[y][x], Math.max(dp[sum][y][x-1],dp[sum-1][y][x-1]+v[y][x]));
					ans=Math.max(ans, dp[sum][y][x]);
				}
			}
		}
		System.out.println(ans);
	}
	
	void tr(Object...o) {System.out.println(Arrays.deepToString(o));}
}


Measured memory_bytes: 413164