akhauriyash/Code-Regression huggingface dataset:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    s = ord("A")
    ss = S()
    ans = [chr(ord("A") + (ord(i) - ord("A") + n) % 26) for i in ss]
    print("".join(ans))
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 40816
def solve(n, xxx):
    n2 = n ** 2
    yyy = sorted((x - 1, k) for k, x in enumerate(xxx, start=1))

    i = 0
    ans = [-1] * n2
    for x, k in yyy:
        j = k - 1
        while j:
            while ans[i] != -1:
                i += 1
            ans[i] = k
            i += 1
            j -= 1
        if i > x:
            return False
        ans[x] = k

    for x, k in yyy:
        while i < n2 and ans[i] != -1:
            i += 1
        if i < x:
            return False
        j = n - k
        while j:
            while i < n2 and ans[i] != -1:
                i += 1
            if i == n2:
                return False
            ans[i] = k
            i += 1
            j -= 1

    return ans


n = int(input())
xxx = list(map(int, input().split()))
result = solve(n, xxx)
if result:
    print('Yes')
    print(*result)
else:
    print('No')


Measured memory_bytes: 10928
#include <bits/stdc++.h>
using namespace std;
#ifdef ENABLE_DEBUG
#define DEBUG(a) cerr<<#a<<"="<<a<<endl
#define DEBUG_ARRAY(a,n) cerr<<#a<<"["<<n<<"]="<<a[n]<<endl
#else
#define DEBUG(a) 
#define DEBUG_ARRAY(a,n) 
#endif
#define FOR(i, a, b) for(int i = a;i < b;i++)
#define For(i, a) FOR(i, 0, a)
#define REV(i, a, b) for(int i = b-1;i >= a;i--)
#define Rev(i, a) REV(i, 0, a)
#define REP(a) For(i, a)

typedef long long int ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<ll, ll> P;
typedef pair<ll,P> PP;
typedef vector<ll> vll;

const ll INF=(1LL<<50);
ll dp[200000][5];
ll f(ll Ai,ll j){
    if(Ai>0){
        if(j==0||j==4)
            return Ai;
        if(j==1||j==3)
            return Ai%2;
        return (Ai+1)%2;
    }else{
        if(j==0||j==4)
            return 0;
        if(j==1||j==3)
            return 2;
        return 1;
    }
}
void solve(long long L, std::vector<long long> A){
    dp[0][4]=dp[0][0]=A[0];
    if(A[0]>0){
        dp[0][3]=dp[0][1]=A[0]%2;
        dp[0][2]=!dp[0][1];
    }else{
        dp[0][3]=dp[0][1]=2;
        dp[0][2]=1;
    }
    REP(L-1){
        For(j,5){
            ll tmp=*min_element(dp[i],dp[i]+j+1);
            dp[i+1][j]=tmp+f(A[i+1],j);
        }
    }
    ll ans=*min_element(dp[L-1],dp[L-1]+5);
    cout<<ans<<endl;

    
}

int main(){
    long long L;
    scanf("%lld",&L);
    std::vector<long long> A(L);
    for(int i = 0 ; i < L ; i++){
        scanf("%lld",&A[i]);
    }
    solve(L, std::move(A));
    return 0;
}


Measured memory_bytes: 9600
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if (a + b > 23) {
            System.out.println(a + b - 24);
        } else {
            System.out.println(a + b);
        }
    }
}

Measured memory_bytes: 21840
def main():
    s = input()
    a = int(s[:2], 10)
    b = int(s[2:], 10)

    print(solve(a, b))

def solve(a, b):
    x = y = False

    if 1 <= a <= 12:
        x = True
    if 1 <= b <= 12:
        y = True
    
    if x and not y:
        return 'MMYY'
    if not x and y:
        return 'YYMM'
    if x and y:
        return 'AMBIGUOUS'
    return 'NA'

main()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,i;
	long long ans=0;
	cin>>n;
	vector <int>a(n);
	vector <int>b(n);
	vector <int>c(n);
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	for(i=0;i<n;i++){
		cin>>b[i];
	}
	for(i=0;i<n;i++){
		cin>>c[i];
	}
	sort(a.begin(),a.end());
	sort(c.begin(),c.end());
	for(i=0;i<n;i++){
		long long j=lower_bound(a.begin(),a.end(),b[i])-a.begin();
		long long k=upper_bound(c.begin(),c.end(),b[i])-c.begin();
		ans+=j*(c.size()-k);
	}
	cout<<ans;
	return 0;
}



Measured memory_bytes: 1408
#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
  int H,W;

  while(cin >> H >> W){
    if(H==0 && W==0){ break; }
    for(int i=0;i<H;i++){
        for(int  j=0;j<W;j++){
            cout << "#";
        }
        cout << endl;
    }
    cout << endl;
  }

  return 0;
}



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

int C[100009];

int main() {
	int N, ans = 0; scanf("%d",&N);
	for(int i=1; i<=N; i++) {
		int foo; scanf("%d",&foo);
		if(foo > N) ++ans;
		else ++C[foo];
	}
	for(int i=1; i<=N; i++) ans += (C[i] >= i ? C[i] - i : C[i]);
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int[] l = new int[3] {s[0]+s[1], s[0]-s[1], s[0]*s[1]};
        Console.WriteLine(l.Max());
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define pp pop_back
#define in insert
#define ff first
#define ss second
#define  show for(int j=0;j<v.size();j++) cout<<v[j]<<" ";
#define ld long double
#define e endl
#define bc __builtin_popcount
#define MOD 1000000007
int main()
{
   int n;
   cin>>n;
   ll a[n];
   for(int i=0;i<n;i++)
     cin>>a[i];
  ll maxi=a[0];
  ll ans=0;
   for(int i=1;i<n;i++)
   {
        if(a[i]<maxi)
        ans+=maxi-a[i];
        maxi=max(maxi,a[i]);
   }
   cout<<ans;
}


Measured memory_bytes: 5168
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mx *max_element
#define mn *min_element
#define fo(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define rfo(i,n) for(ll i=n-1;i>=0;i--)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define precision cout<<fixed<<setprecision(10)
#define mem(x,p) memset(x,p,sizeof(x))
#define w(t) ll t;cin>>t;while(t--)
#define kk "\n"
#define setbits(x) __builtin_popcountll(x)
const double pi=3.1415926535897932384626;
//const ll mod = 998244353;
const ll mod=1e9+7;
int main()
{
  IOS
  ll n;
  cin>>n;
  if(n%1000==0)
  cout<<0;
  else
  {
      n=n%1000;
      cout<<1000-n;
  }
  return 0;
}

Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <queue>
#include <utility>
using namespace std;

const int INF = 1e9;
const int MAX_H = 1e3 + 2;
const int MAX_W = 1e3 + 2;
int H, W, d[MAX_H][MAX_W];
string S[MAX_H];
queue<pair<int, int>> q;

void bfs(){
    while (!q.empty()){
        auto p = q.front(); q.pop();
        int y = p.first;
        int x = p.second;
        if (0   <= y-1 && d[y-1][x] == INF && S[y-1][x] == '.') {q.push(make_pair(y-1, x)); d[y-1][x] = d[y][x] + 1;}
        if (y+1 <= H-1 && d[y+1][x] == INF && S[y+1][x] == '.') {q.push(make_pair(y+1, x)); d[y+1][x] = d[y][x] + 1;}
        if (0   <= x-1 && d[y][x-1] == INF && S[y][x-1] == '.') {q.push(make_pair(y, x-1)); d[y][x-1] = d[y][x] + 1;}
        if (x+1 <= W-1 && d[y][x+1] == INF && S[y][x+1] == '.') {q.push(make_pair(y, x+1)); d[y][x+1] = d[y][x] + 1;}
    }
}

int main() {
    cin >> H >> W;
    for (int i = 0; i < H; ++i){
        for (int j = 0; j < W; ++j){
            d[i][j] = INF;
        }
    }
    for (int i = 0; i < H; ++i){
        cin >> S[i];
        for (int j = 0; j < S[i].length(); ++j){
            if (S[i][j] == '#'){
                q.push(make_pair(i, j));
                d[i][j] = 0;                
            }
        }
    }
    bfs();
    int ans = 0;
    for (int i = 0; i < H; ++i){
        for (int j = 0; j < W; ++j){
            ans = max(ans, d[i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13456
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=(0);(i)<(int)(n);++(i))
#define p(x) cout<<(x)<<endl;
#define pv(v) for(auto a: v){ cout << a << endl; }

int main() {
  int n; cin >> n;
  vector<int> k(2);
  vector<int> h(3);
  vector <vector<int>> ls(n);
  vector <vector<int>> ss;

  rep(i, n){
    int a, b;
    cin >> a >> b;
    k[0] = a;
    k[1] = b;
    ls[i] = k;
  }

  if (n == 1) {p(1); return 0;}

  rep(i, n){
    rep(j, n){
      if (j != i) {
        int x,y;
        x = ls[i][0];
        y = ls[i][1];

         int xx,yy;
        xx = ls[j][0];
        yy = ls[j][1];
        
        h[0] = xx-x;
        h[1] = yy-y;
        h[2] = 0;

        int flag = 0;
        for (int z = 0; z < ss.size(); z ++) {
          if (ss[z][0] == xx-x && ss[z][1] == yy-y) {
            ss[z][2]++;
            flag = 1;
          }    
        }
        if (flag == 0) {
          ss.push_back(h);
        }
      
      }
    }
  }  

  int count = 0;
  for(int o = 0; o < ss.size(); o++) {
    count = max(count, ss[o][2]);
  }

  p(n - (count + 1));
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n,ans=0,h;
    cin>>h;
    n=1;
    while(h>0)
    {
        h/=2;
        ans+=n;
        n*=2;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
    #include<string.h>
    using namespace std;
    #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define endl "\n"
    #define Max(x,y,z) max(x,max(y,z))
    #define Min(x,y,z) min(x,min(y,z))
    #define fr(i,s,e) for(i=s;i<e;i++)
    #define rf(i,s,e) for(i=s-1;i>=e;i--)
    #define pb push_back
    #define eb emblace_back
    #define mp make_pair
    #define ff first
    #define ss second
    #define ll long long
    #define trace1(x)                cerr<<#x<<": "<<x<<endl
    #define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
    #define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
    #define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
    #define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
    #define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
    #define vl vector<long long>
     
    #define vi vector<int> 
    #define vii vector< vector<int> >
	#define viii vector<vector<vector<int> > > 
    #define vll vector< vector<long long> >
    #define vpi vector< pair<int,int> >   
    #define vpl vector< pair<ll,ll> >   
    typedef pair<pair<int, int>,int> P;
     #define mod %1000000007
     //#define p 41
    bool less_vectors(const vector<int>& a,const vector<int>& b) 
    {
       return a.size() > b.size();
    }
     
    ll gcd(ll a,ll b)
	{
	if(a%b==0)
		return b;
		else
			return gcd(b,a%b);
	}
	bool cmp(pair<char,int> p1,pair<char,int>  p2)
    {
		if(p1.ff!=p2.ff)
    		return p1.ff>p2.ff;
			else
				return p1.ss<p2.ss;
    }
	ll fastexpo(ll a,ll b)
	{
		//trace2(a,b);
    	ll res=1;
    	while(b>0)
    	{
    		if(b%2==1)
    			res=(((res)mod)*((a)mod))mod;
    		a=(((a)mod)*((a)mod))mod;
    		b/=2;
    	}
		//trace1(res);
    	return res;
	}
	ll fastexpom(ll a,ll b,ll m)
	{
	ll res=1;
    	while(b>0)
    	{
    		if(b%2==1)
    			res=(((res)%m)*((a)%m))%m;
    		a=(((a)%m)*((a)%m))%m;
    		b/=2;
    	}
    	return res;
	}
	ll modinv(ll a,ll m)
	{
	return fastexpom(a,m-2,m);
	}
int main()
{
	IOS;
	int n;
	cin>>n;
	vl v(n);
	for(int i=0;i<n;i++)
		cin>>v[i];
	sort(v.begin(),v.end());
	ll a=-1;
	ll b=-1;
	for(int i=n-2;i>=0;i--)
	{
		//trace3(i,v[i],v[i-1]);
		if(v[i]==v[i+1])
		{
			if(a==-1)
				{a=v[i];
				i--;
				}
				else
					if(b==-1)
					{
						b=v[i];
						break;
					}
		}
	}
	ll ans=0;
	
	ans=max(ans,a*b);
	if(a==-1 || b==-1)
		ans=0;
	cout<<ans;
	return 0;

}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

const LL MOD = 1000000000 + 7LL;

int main() {
	int N, M;
	cin >> N >> M;
	if (abs(N - M) > 1) {
		cout << 0 << endl;
		return 0;
	}
	LL facN = 1LL;
	LL facM = 1LL;
	FOR (i, N) {
		facN *= (i + 1);
		facN %= MOD;
	}

	FOR (i, M) {
		facM *= (i + 1);
		facM %= MOD;
	}
	LL ret = (facN * facM) % MOD;
	if (N == M)
		ret *= 2LL;
	ret %= MOD;
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,M;
  cin>>N>>M;
  vector<int> H(N);
  vector<bool> A(N,true);
  for(int &i:H)
    cin>>i;
  while(M--){
    int a,b;
    cin>>a>>b;
    a--,b--;
    if(H[a]>=H[b])
      A[b]=false;
    if(H[a]<=H[b])
      A[a]=false;
  }
  int j=0;
  for(bool bo:A)
    if(bo)
      j++;
  cout<<j<<endl;
}

Measured memory_bytes: 3752
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    if(b-a == c-b){
      System.out.println("YES");
    }else{
      System.out.println("NO");
    }
  }
}

Measured memory_bytes: 21716
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <set>
#include <vector>
#include <queue>

using namespace std;

typedef long long ll;
typedef long double ld;

constexpr int INF = 1e9;
constexpr ll BIGINF = 1e18;
constexpr double EPS = 1e-16;

void preambule() {
  cin.tie(0);
  cout.precision(16);
  cout << fixed;
}

string s;
string t;

int a;
int b;

string u;

void input() {
  cin >> s >> t >> a >> b >> u;
}

void solve() {
  if (u == s) {
    --a;
  } else {
    --b;
  }

  cout << a << ' ' << b << '\n';
}

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  preambule();
  input();
  solve();
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=25005,K=405,mod=1e9+7;
int n,m,k,p[N],pos[K];
ll ans,f[N][K],g[N][K],a[K],b[K];
ll power(ll a,ll b){
	ll res=1,tmp=a;
	while(b){
		if(b%2)res=res*tmp%mod;
		tmp=tmp*tmp%mod;
		b>>=1;
	}
	return res;
}
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=m;i++)
		scanf("%d",&p[i]);
	int cnt=0;
	for(int i=1;i<=m;i++){
		cnt=max(cnt,pos[p[i]]);
		pos[p[i]]=i;
		if(cnt+k==i){
			printf("%lld",(n-m+1)*power(k,n-m)%mod);
			return 0;
		}
	}
	if(cnt==0){
		f[0][0]=1,g[0][0]=0;
		for(int i=1;i<=n;i++){
			for(int j=k;j>=1;j--){
				a[j]=(a[j+1]+f[i-1][j])%mod;
				b[j]=(b[j+1]+g[i-1][j])%mod;
			}
			for(int j=1;j<=k;j++){
				f[i][j]=(f[i-1][j-1]*(k-j+1)+a[j])%mod;
				g[i][j]=(g[i-1][j-1]*(k-j+1)+b[j])%mod;
			}
			for(int j=1;j<=k;j++){
				if(j>=m){
					if(j==k)f[i][j]=g[i][j]=0;
					else g[i][j]=(g[i][j]+f[i][j])%mod;
				}
			}
		}
		for(int i=1;i<k;i++)ans=(ans+g[n][i])%mod;
		for(int i=k-m+1;i<=k;i++)ans=ans*power(i,mod-2)%mod;
		printf("%lld",((n-m+1)*power(k,n-m)-ans+mod)%mod);
	}
	else{
		int num1,num2;
		memset(pos,0,sizeof(pos));
		for(int i=1;i<=m;i++){
			if(pos[p[i]]){
				num1=i-1;
				break;
			}pos[p[i]]=i;
		}
		memset(pos,0,sizeof(pos));
		for (int i=m;i>=1;i--){
			if(pos[p[i]]){
				num2=m-i;
				break;
			}pos[p[i]]=i;
		}
		f[0][num1]=g[0][num2]=1;
		for(int i=1;i<=n;i++){
			for(int j=k;j>=1;j--){
				a[j]=(a[j+1]+f[i-1][j])%mod;
				b[j]=(b[j+1]+g[i-1][j])%mod;
			}
			for(int j=1;j<k;j++){
				f[i][j]=(f[i-1][j-1]*(k-j+1)+a[j])%mod;
				g[i][j]=(g[i-1][j-1]*(k-j+1)+b[j])%mod;
			}
		}
		for(int i=0;i+m<=n;i++){
			ll s1=0,s2=0;
			for (int j=0;j<=k;j++){
				s1=(s1+f[i][j])%mod;
				s2=(s2+g[n-m-i][j])%mod;
			}
			ans=(ans+s1*s2)%mod;
		}
		printf("%lld",((n-m+1)*power(k,n-m)-ans+mod)%mod);
	}
	return 0;
}

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

const int N = 1e5+5, M = 1e6+6, OO = 0x3f3f3f3f;
 ll q, h, s, d;
 ll n;
 set<ll> st;
 vector<ll> v;
void brute(ll sum, ll litres)
{
    if(litres  == 0)
    {
        cout<<sum<<endl;
        // st.insert(sum);
        v.push_back(sum);
        return;
    }
    if(litres < 0)
        return;
    if(litres >= 1)
        brute(sum + q, litres - 1 );
    if(litres >= 2)
        brute(sum + h, litres - 2);
    if(litres >= 4)
        brute(sum + s, litres - 4 );
    if(litres >= 8)
        brute(sum + d, litres - 8 );
}
int main()
{
    cin>>q>>h>>s>>d>>n;
    h = min(h, q*2);
    s = min(s, h*2);
    d = min(d, s*2);
    n*= 4;
    ll ans = 0;
    ans+= (n/8)  * d;
    n%= 8;
    ans+= (n/4) * s;
    n%= 4;
    ans+= (n/2) * h;
    n%= 2;
    ans+= n* q;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
q, h, s, d = map(int, input().split())
n = int(input())
ans = 0
q_per = q / 0.25
h_per = h / 0.5
s_per = s
d_per = d / 2
list = [q_per,h_per,s_per,d_per]
if min(list) == d_per :
    if n%2 == 0:
        ans += d * (n //2)
    else :
        ans += n//2 * d
        n -= n//2
        list.remove(d_per)
        if min(list) == s_per :
            ans += s_per
        elif min(list) == h_per :
            ans += h * 2
        else :
            ans += q * 4
elif min(list) == s_per :
    ans += n * s
elif min(list) == h_per :
    ans += n * 2 * h
else :
    ans += n * 4 * q

print(int(ans))


Measured memory_bytes: 9228
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

signed main(){
  int n,h;
  cin>>n>>h;
  vector<int> B(n);
  int max_A=-INF;
  REP(i,n){
    int a,b;
    cin>>a>>b;
    B[i]=b;
    max_A=max(max_A,a);
  }
  sort(ALL(B));
  reverse(ALL(B));
  int ans=0;
  REP(i,n){
    if(B[i]>=max_A){
      h-=B[i];
      ans++;
      if(h<=0){
        cout<<ans<<endl;
        return 0;
      }
    }
  }
  cout<<(h%max_A==0?h/max_A+ans:h/max_A+1+ans)<<endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

typedef enum {false, true} bool;


bool trace(long long xy[][2], long long basis, int N, int num, int ctr, int index)
{
    int i, j;
    static int record[15];
    static bool flag;
    
    
    if(num == ctr)
    {
        flag = true;
        
        for(i=0; i<num; i++)
        {
            if((xy[record[i]][1] & basis) != basis || ((xy[record[i]][0] ^ ~basis) & ~basis) != ~basis)
            {
                flag = false;
                
                break;
            }
        }
    }
    else
    {
        for(j=index; j<=N-(num-ctr); j++)
        {
            if(ctr == 0)
                basis = 0;
            
            record[ctr] = j;
            
            if(trace(xy, basis | 1<<(N-j-1), N, num, ctr+1, j+1))
                return true;
        }
    }
    
    if(flag)
        return true;
    else
        return false;
}

int main(void)
{
    char c;
    int N;
    int A, x, y;
    
    long long xy[15][2], temp;
    
    int i, j;
    
    
    scanf("%d%c", &N, &c);
    
    
    for(i=0; i<N; i++)
    {
        scanf("%d%c", &A, &c);
        
        xy[i][0] = 1<<(N-i-1);
        
        xy[i][1] = 1;
        for(j=1; j<N; j++)
            xy[i][1] = xy[i][1]<<1 | 1;
        
        temp = xy[i][1];
        
        for(j=0; j<A; j++)
        {
            scanf("%d%c%d%c", &x, &c, &y, &c);
            
            if(y == 0)
                xy[i][1] &= temp ^ 1<<(N-x);
            
            if(y == 1)
                xy[i][0] |= 1<<(N-x);
        }
    }
    
    for(i=N; i>0; i--)
    {
        if(trace(xy, 0, N, i, 0, 0))
            break;
    }
    
    
    printf("%d\n", i);
    
    
    //system("pause");
    
    return 0;
}


Measured memory_bytes: 128
A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0

for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            money = 500 * i + 100 * j + 50 * k
            if money == X:
                ans += 1

print(ans)

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
//		List<String> divisor = new ArrayList<>();
//		int[] in = Stream.of(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
//		int x = Integer.parseInt(sc.next());
//		int S = Integer.parseInt(sc.next());
//		String[] S = sc.next().split("");
		String s = sc.next();
		String res = s.substring(s.indexOf("A"), s.lastIndexOf("Z") + 1);
		
//		for (int i = 1; i <= N; i++) {
//		}
		
		System.out.println(res.length());		
	}
}


Measured memory_bytes: 26724
#include <iostream>                                             
#include <vector>                                               
using namespace std;                                            
                                                                
int main() {                                                    
  int n, m;                                                     
  while (true) {                                                
    cin >> n;                                                   
    if (n==0) {                                                 
      break;                                                    
    }                                                           
    vector<char> from(n);                                       
    vector<char> to(n);                                         
    for (int i=0; i<n; i++) {                                   
      cin >> from[i] >> to[i];                                  
    }                                                           
    cin >> m;                                                   
    vector<char> v(m);                                          
    for (int i=0; i<m; i++) {                                   
      cin >> v[i];                                              
      for (int j=0; j<n; j++) {                                 
        if (v[i]==from[j]) {                                    
          v[i] = to[j];                                         
          break;                                                
        }                                                       
      }                                                         
    }                                                           
    for (int i=0; i<m; i++) {                                   
      cout << v[i];                                             
    }                                                           
    cout << "\n";                                               
  }                                                             
  return 0;                                                     
}                                                               
                              

Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
#define int long long

int gcd(int a, int b)
{
    if (a < b) {
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return b ? gcd(b, a % b) : a;
}

main() {
  int a,b;
  cin >> a >> b;
  int c = a*b;
  int ans;
  ans = c / gcd(a,b);
  cout << ans;
  return 0;
}


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

bool ans;

void solve(int cntnum[],int progress){
    int cntnum_c[10],cntcont=0;

    /*printf("%d: ",progress);
    for(int i=0;i<10;i++){
        printf("%d",cntnum[i]);
    }puts("");*/

    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++) cntnum_c[j]=cntnum[j];
        if(cntnum[i] >= 1){
            cntcont++;
        }
        else cntcont=0;
        if(cntnum[i] >= 2 && progress == 0){
            cntnum_c[i]-=2;
            solve(cntnum_c,progress+1);
        }
        if(progress >= 1){
            if(cntcont >= 3){
                if(progress == 4){
                    ans = true;
                    return;
                }
                for(int j=i-2;j<=i;j++) cntnum_c[j]--;
                solve(cntnum_c,progress+1);
            }
            else if(cntnum[i] >= 3){
                if(progress == 4){
                    ans = true;
                    return;
                }
                cntnum_c[i]-=3;
                solve(cntnum_c,progress+1);
            }
        }
    }
    return;
}

int main(){
    char input;
    while(cin >> input){
        int cntnum[10]={},cntans=0,outputans[10];
        input-='0';
        cntnum[input]++;
        for(int i=1;i<13;i++){
            scanf(" %c",&input);
            input-='0';
            cntnum[input]++;
        }
        for(int i=1;i<10;i++){
            ans=false;
            cntnum[i]++;
            if(cntnum[i] < 5)solve(cntnum,0);
            cntnum[i]--;
            if(ans){
                outputans[cntans]=i;
                cntans++;
            }
        }
        if(cntans ==0) printf("0\n");
        else{
            printf("%d",outputans[0]);
            for(int i=1;i<cntans;i++){
                printf(" %d",outputans[i]);
            }puts("");
        }
    }

    return 0;
}

Measured memory_bytes: 1156
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
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 <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;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    int N, K, X, Y;
    cin >> N >> K >> X >> Y;
    if (N <= K) {
        cout << X * N << endl;
    } else {
        cout << X * K + (N - K) * Y << endl;
    }
}


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

int main() {
  string s;
  cin >> s;
  int ans;
  if (s == "SUN")
    ans = 7;
  else if (s == "MON")
    ans = 6;
  else if (s == "TUE")
    ans = 5;
  else if (s == "WED")
    ans = 4;
  else if (s == "THU")
    ans = 3;
  else if (s == "FRI")
    ans = 2;
  else if (s == "SAT")
    ans = 1;

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

Measured memory_bytes: 256
s=input()
l=[["x",-1]]
for i in range(len(s)):
    if s[i]!="x":
        l.append([s[i],i])
a=0
l.append(["x",len(s)])
for i in range(1,-(-len(l)//2)):
    if l[i][0]==l[-i-1][0]:
        a+=abs(l[i][1]-l[i-1][1]+l[-i-1][1]-l[-i][1])
    else:
        a=-1
        break
print(a)

Measured memory_bytes: 16500
#include <bits/stdc++.h>
using namespace std;
#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 repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define cauto const auto
#ifdef LOCAL
#define dump(...) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] ", _dmp_(#__VA_ARGS__, __VA_ARGS__);
void _dmp_(const char*) { cerr << endl; }
template <class T, class... U>
void _dmp_(const char *s, T const& x, U const& ...y) { const char *o = "({[", *e = "]})"; for (int i = 0; *s != '\0'; cerr << *s++) { if (count(o,o+3,*s)) i++; if (count(e,e+3,*s)) i--; if (!i && *s == ',') break; } cerr << " = " << x; if (*s == ',') cerr << ", ", s++; _dmp_(s, y...); }
#else
#define dump(...)
#endif
using ll = long long;
#define int ll
template <class T> using pque_max = priority_queue<T>;
template <class T> using pque_min = priority_queue<T, vector<T>, greater<T> >;
#define CONAINER_OUTPUT os << "{"; for (auto const& x : v) os << " " << x; return os << " }";
template <class T> ostream& operator<<(ostream& os, vector<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, deque<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, set<T> const& v) { CONAINER_OUTPUT }
template <class T, class U> ostream& operator<<(ostream& os, map<T,U> const& v) { CONAINER_OUTPUT }
#undef CONAINER_OUTPUT
template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class T, class S> istream& operator>>(istream& is, pair<T,S> const& p) { return is >> p.first >> p.second; }
struct _Init_ { _Init_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); } } _init_;

template <class T> void quit(T const& x) { cout << x << endl; exit(0); }
template <class T> bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; }
template <class T> bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }
#define YesNo(c) ((c) ? "Yes" : "No")
////////////////////////////////

int mod(int x, int m) { return (x%m+m)%m; }

int32_t main() {
    int n,x; cin >> n >> x;
    vector<int> a(n); cin >> a;
    vector<int> b = a;
    int mi = 1e13;
    rep (k,n) {
        rep (i,n) chmin(b[i],a[mod(i-k,n)]);
        chmin(mi, x*k + accumulate(all(b),0LL));
    }
    cout << mi << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(){
  int a=10;
  int b=10;
  while(a+b){
  	vector<int> size(3);
    vector<int> val(3);
  	vector<vector<int>> data(3);
    vector<vector<int>> now(3,vector<int>(15,0));
    cin >> a >>b;
    if(a+b==0)break;
    rep(i,3){
      int c;
      cin >> c;
      size[i] = c;
      rep(j,c){
        int x;
        cin >> x;
        data[i].push_back(x);
      }
    }
    /*rep(i,3){
      rep(j,data[i].size()){
        cout << data[i][j] << " ";
      }
      cout << endl;
    }*/
    int ret=INF; 
    if(size[0]==a||size[2]==a)ret=0;
		for(int m=0;m<2;m++){
			int last=m;
			for(int i=0;i<3;i++){
				val[i]=size[i];
				for(int j=0;j<size[i];j++)now[i][j]=data[i][j];
			}
			int k=0;
			while(k<b&&val[0]!=a&&val[2]!=a){
				if(val[last+1]&&(val[last]==0||now[last][val[last]-1]<now[last+1][val[last+1]-1])){
					now[last][val[last]++]=now[last+1][--val[last+1]];
				}else{
					now[last+1][val[last+1]++]=now[last][--val[last]];
				}
				last=!last;
				k++;
				//printf("%d %d %d\n",val[0],val[1],val[2]);
			}
			if(val[0]==a||val[2]==a)ret=min(ret,k);
		}
		if(ret==INF)printf("-1\n");
		else printf("%d\n",ret);
	}
}


Measured memory_bytes: 3224
n = gets.to_i
a = gets.chomp.split(" ").map(&:to_i)
path = []
path[0..1] = [0,(a[1]-a[0]).abs]
for i in 2..n-1
  path[i] = [path[i-2]+(a[i]-a[i-2]).abs,path[i-1]+(a[i]-a[i-1]).abs].min
end
puts path[-1]

Measured memory_bytes: 11908
<?php

fscanf(STDIN, '%s', $W);

$W = strtolower($W);
$T = array();
$cnt = 0;

while (($line = trim(fgets(STDIN))) !== '') {
    if ($line === 'END_OF_TEXT') {
        break;
    }

    $line = strtolower($line);
    foreach (explode(' ', $line) as $T) {
        if ($W === $T) {
            $cnt++;
        }
    }
}

echo $cnt, PHP_EOL;

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

int main() {
    int n;
    cin >> n;
    
    string s,t;
    cin >> s >> t;

    int ans=0;
    if(s==t){
        ans=n;
    }
    else{
        int cnt=0;
        for (int i = 0; i < n; i++){
            if(s.substr(n-1-i)==t.substr(0,i+1)){
                cnt=i+1;
            }
        }
        ans=2*n-cnt;
    }
    cout << ans << endl;
}

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

int main(){
  ll h,w,tmp;
  cin >> h >> w;
  if(h!=w){
    tmp=min(h,w);
    h=max(h,w);
    w=tmp;
  }
  //cout << h << endl;
  if(h%3==0 || w%3==0){
    cout << '0' << endl;
    return 0;
  }
  ll san=h/3;
  ll ans=0;
  ans+=w;
  ll half=w/2-1;
  for(int i=0;i<w;++i){
    vector<ll> s(3);
    s[0]=i*h;
    if(h%2!=0){
      s[1]=(w-i)*(h/2);
      s[2]=(w-i)*(h/2+1);
    }else{
      s[1]=(w-i)*(h/2);
      s[2]=(w-i)*(h/2);
    }
    sort(s.begin(),s.end());
    ans=min(ans,s[2]-s[0]);
    //cout << ans << endl;
  }
  //san=h/3;
  ans=min(ans,h);
  //cout << ans << endl;
  half=h/2-1;
  for(int i=0;i<h;++i){
    vector<ll> s(3);
    s[0]=i*w;
    if(w%2!=0){
      s[1]=(h-i)*(w/2);
      s[2]=(h-i)*(w/2+1);
    }else{
      s[1]=(h-i)*(w/2);
      s[2]=(h-i)*(w/2);
      //cout << s[2] << endl;
    }
    sort(s.begin(),s.end());
    ans=min(ans,s[2]-s[0]);
    //cout << ans << endl;
  }
  cout << ans << endl;
  return 0;

}


Measured memory_bytes: 256
#include <stdio.h>
int T;
int gcd(int x, int y) {
	if(x == 0) return y;
	if(y == 0) return x; T++;
	if(x > y) return gcd(y, x % y);
	return gcd(x, y % x);
}
int main() {
    int a,b;
	while(true) {
		scanf("%d%d",&a,&b); T = 0;
		if(a==0&&b==0) return 0;
		a=gcd(a,b);
		printf("%d %d\n",a, T);
	}
}



Measured memory_bytes: 2604
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <map>
using namespace std;


int main()
{
    int n, x;
    cin >> n >> x;
    vector<int> l(n);
    for (int i = 0 ; i < n; i++) {
        cin >> l[i]; 
    }
    int now = 0;
    int res = 1;
    for (int i = 2; i <= n + 1; i++) {
        now += l[i - 2];
        if (now > x) {
            break;
        }
        res = i;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
N = int(input())
L = list(map(int,input().split()))
cnt = [0 for i in range(1001)]
for l in L:
	cnt[l] += 1
total = [0 for i in range(1001)]
for i in range(1, 1001):
	total[i] = total[i-1] + cnt[i]

ans = 0
for i in range(1, 1001):
	if cnt[i] <= 0:
		continue
	I = cnt[i]
	for j in range(i, 1001):
		J = cnt[j]
		if J <= 0:
			continue
		if i == j and J <= 1:
			continue
		base = (I * (I - 1)) // 2 if i == j else I * J
		M = min(1000, i + j - 1)
		if i == j:
			if cnt[j] >= 3:
				ans += (I * (I-1) * (I-2)) // 6
		elif cnt[j] >= 2:
			ans += I * (J * (J-1)) // 2
		ans += base * (total[M] - total[j])
print(ans)


Measured memory_bytes: 3188
package main

import (
	"fmt"
)

func makeDp(iLen, jLen int) [][]int {
	dp := make([][]int, iLen)
	for i := range dp {
		dp[i] = make([]int, jLen)
	}
	return dp
}

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

func reverse(bs []byte) {
	var beforeHarfStart, afterHarfStart, loopCnt int
	length := len(bs)
	if length%2 == 0 {
		beforeHarfStart = length/2 - 1
		afterHarfStart = length / 2
		loopCnt = length / 2
	} else {
		beforeHarfStart = (length - 1) / 2
		afterHarfStart = (length - 1) / 2
		loopCnt = (length + 1) / 2
	}

	for i := 0; i < loopCnt; i++ {
		s1 := bs[beforeHarfStart-i]
		s2 := bs[afterHarfStart+i]
		bs[beforeHarfStart-i] = s2
		bs[afterHarfStart+i] = s1
	}
}

func extract(s, t string) string {
	sLen, tLen := len(s), len(t)
	// Definition of DP
	//var dp [3001][3001]int
	dp := makeDp(sLen+1, tLen+1)

	for i := 0; i < sLen; i++ {
		for j := 0; j < tLen; j++ {
			if s[i] == t[j] {
				dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
			}
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])
		}
	}

	var result []byte
	i, j := sLen, tLen
	for i > 0 && j > 0 {
		if dp[i][j] == dp[i-1][j] {
			// (i-1, j) -> (i, j) と更新されていた場合
			i-- // DP の遷移を遡る
		} else if dp[i][j] == dp[i][j-1] {
			// (i, j-1) -> (i, j) と更新されていた場合
			j-- // DP の遷移を遡る
		} else {
			// (i-1, j-1) -> (i, j) と更新されていた場合
			result = append(result, s[i-1]) // このとき s[i-1] == t[j-1] なので、t[j-1] + res でも OK
			i--                             // DP の遷移を遡る
			j--
		}
	}

	reverse(result)
	return string(result)
}

func main() {
	var s, t string
	fmt.Scan(&s)
	fmt.Scan(&t)

	fmt.Println(extract(s, t))
}


Measured memory_bytes: 75392
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
     cin >>n;
    int num[4][3][10] = {};
    for (int i =0;i<n;i++){
         int b,f,r,v;
         cin >>b>>f>>r>>v;
         num[b-1][f-1][r-1]+= v;
     }
      
     for ( int i =0 ; i<4;i++){
         if(i) cout<<"####################"<<endl;
         for (int j =0;j<3;j++){
         
         for(int k =0;k<10;k++){
             cout << " "<<num[i][j][k];
         }
         cout <<endl;
         }
    }
  return 0;
}


Measured memory_bytes: 3100
//(・ω・)
#include <stdio.h>
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, atoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <iomanip> //setprecision
#include <limits>
#include <sstream> //istringstream
#include <stdlib.h>
#include <list>
#include <iterator>//std::advance()
using namespace std;

int main(){
   int n;
    cin >> n;
    n%=10;
    if(n==3) cout << "bon" << endl;
    else if(n==0 || n==1 || n==6 || n==8) cout << "pon" << endl;
    else cout << "hon" << endl;
}


Measured memory_bytes: 3636
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  string a;
  cin >> a;
  cout << a.front() << a.size() - 2 << a.back() << endl;

  return 0;
}


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

int i,j,ppp,line[9];
char row[9];

int main(){
	while(1){
		for(i=0;i<3;i++){
			scanf("%s",row);
			if(row[0]=='0')return 0;
			for(j=0;j<3;j++){
				if(row[j]=='w')ppp=1;
				else if(row[j]=='b')ppp=-1;
				else continue;
				line[j]+=ppp;
				line[3+i]+=ppp;
				if(i==j)line[6]+=ppp;
				if(i==2-j)line[7]+=ppp;
			}
		}
		for(i=0;i<8;i++){
			if(line[i]==3){printf("w\n");break;}
			if(line[i]==-3){printf("b\n");break;}
			line[i]=0;
		}
		if(i==8)printf("NA\n");
		for(;i<8;i++)line[i]=0;
	}
	return 0;
}

Measured memory_bytes: 524
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define ll          long long
#define pb          push_back
#define INF         9223372036854775807
#define    endl        '\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)    for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define lower(u)    transform(u.begin(), u.end(), u.begin(), ::tolower);//convert string u to lowercase;
#define upper(u)    transform(u.begin(), u.end(), u.begin(), ::toupper);
using namespace std;

using namespace __gnu_pbds; 
  
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define N  5005
vi adj[N];
ll n,k;
ll p[N];
ll c[N];
vi v;
bool vis[N];
void dfs(ll n,ll csum)
{
    vis[n]=1;
    for(auto u:adj[n])
    {
        if(!vis[u])
        {
            v.pb(csum+c[u]);
            dfs(u,csum+c[u]);
        }
    }

}
void solve()
{
    cin>>n>>k;
    rep(i,1,n+1)
    {
        cin>>p[i];
        adj[i].pb(p[i]);
    }
    rep(i,1,n+1)
    {
        cin>>c[i];
    }
    ll ans=-1e15;
    rep(i,1,n+1)
    {
        memset(vis,0,sizeof(vis));
        dfs(i,0);
        v.pb(v.back()+c[i]);
        ll yebhi=*max_element(all(v));
        ll res=v.back();
        ll x=(k-1)/v.size();
        ll y=k-(x*v.size());

        ll final=x*(max(res,0ll));
        ll resi=-1e15;
        rep(j,0,y)
        {
            resi=max(resi,v[j]);
        }
        final+=resi;
        if(k>=v.size())
        final=max(final,yebhi);
        ans=max(ans,final);
        v.clear();
    }
    cout<<ans<<endl;

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4492
// ABC162A.cpp : コンソール アプリケーションのエントリ ポイントを定義します。
//

#include <iostream>

void solve_A() {
	int N; std::cin >> N;
	int mod_1 = N % 10;
	N /= 10;
	int mod_2 = N % 10;
	N /= 10;
	int mod_3 = N % 10;
	N /= 10;
	if (mod_1 == 7 || mod_2 == 7 || mod_3 == 7) {
		std::cout << "Yes";
	}
	else {
		std::cout << "No";
	}

}

void solve_B() {
	int N;
	std::cin >> N;

	long long int sum = 0;
	for (int i = 1; i <= N; i++) {
		if (i % 3 != 0 && i % 5 != 0) {
			sum += i;
		}
	}
	std::cout << sum;
}

int gcd(int y, int x) {
	if (y < x) std::swap(x, y);
	int r;
	while (x > 0) {
		r = y % x;
		y = x;
		x = r;
	}

	return y;

}

void solve_C(){
	int K;
	std::cin >> K;

	int sum = 0;
	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= K; j++) {
			for (int k = 1; k <= K; k++) {
				sum += gcd(gcd(i, j), k);
			}
		}
	}

	std::cout << sum;

}

#include <string>
void solve_D() {
	int n;
	std::cin >> n;
	std::string s;
	std::cin >> s;
	long long r_count = 0, g_count = 0, b_count = 0;
	for(int i = 0; i < n;i++) {
		if (s[i] == 'R') r_count++;
		else if (s[i] == 'G') g_count++;
		else b_count++;
	}
	long long ans = r_count * g_count * b_count;
	for (int distance = 1; distance < n + 1; distance++) {
		for (int j = 0; j + 2 * distance < n; ++j) { 
			if (s[j] != s[j + distance] && s[j + distance] != s[j + 2 * distance] && s[j] != s[j + 2 * distance])
				ans -= 1;
		}
	}
	std::cout << ans << std::endl;
}

const long long MOD = 1e9 + 7;
long long pwr(long long a, long long n) {
	a %= MOD;
	long long r = 1;
	for (; n > 0; n >>= 1) {
		if (n & 1) r = r * a % MOD;
		a = a * a % MOD;
	}
	return r;
}

void solve_E() {
	int n, k; std::cin >> n >> k;
	long long  answer = 0;
	const int N = 1e5 + 10;
	long long ways[N];
	for (int x = k; x >= 1; x--) {
		int m = k / x;
		ways[x] = pwr(m, n);
		for (int gg = 2 * x; gg <= k; gg += x) {
			ways[x] -= ways[gg];
		}
		ways[x] %= MOD;
		ways[x] += MOD;
		ways[x] %= MOD;

		answer += (ways[x] * x) % MOD;
	}
	answer %= MOD;
	std::cout << answer << std::endl;
}

#include<algorithm>
void solve_F() {
	int n;
	long long A[200001], dp[200001], sum[200001];
	//long long A[100], dp[100], sum[100];
	std::cin >> n;
	dp[0] = dp[1] = 0;
	sum[0] = sum[1] = 0;
	for (int i = 1; i <= n; i++) {
		std::cin >> A[i];
		if(i==1){
			sum[i] = A[i];
			continue;
		}
		sum[i] = sum[i - 2] + A[i];
	}

	for (int i = 2; i <= n; i++) {
		if (i%2==0) {
			dp[i] = std::max(dp[i - 2] + A[i], sum[i-1]);
		}
		else if (i%2 == 1) {
			dp[i] = std::max(dp[i - 2] + A[i], dp[i-1]);
		}
	}

	std::cout << dp[n] << std::endl;

}


int main()
{
	std::ios::sync_with_stdio(false);
	//solve_A();
	//solve_B();
	//solve_C();
	//solve_D();
	//solve_E();
	solve_F();
    return 0;
}



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


int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        int ans=0;
        for(int i=1;i<n;i++){
            int a=i;
            int k=0;
            while(k<n){
                k+=a;
                a++;
            }
            if(k==n) ans++;
        }
        cout<<ans<<endl;
    }
    
    
}


Measured memory_bytes: 3052
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int sum = 0;
		char ans[] = sc.next().toCharArray();		
		char board[][] = new char[n][];
		
		for(int i = 0; i < n; i++){
			board[i] = sc.next().toCharArray();
		}
		
		for(int i = 0; i < n; i++){
			search:for(int k = 0; k < board[i].length; k++){
				if(board[i][k] == ans[0]){
					for(int j = k+1; j < board[i].length; j++){
						if(board[i][j] == ans[1]){
							int diff = j - k;
							int a = 2;
							int c = 2;
							for(int h = j + diff; h < board[i].length; h += diff){
								if(board[i][h] == ans[a] && c == ans.length - 1){
									sum++;
									break search;
								}else if(board[i][h] == ans[a]){
									c++;
									a++;
								}else{
									break;
								}
							}
						}
					}
				}
			}
		}
		System.out.println(sum);
	}

}

Measured memory_bytes: 27660
package main

import (
	"fmt"
)


func main() {
	var N, K int
	fmt.Scanf("%d %d", &N, &K)

	var a, b int
	var array [100001]int
	for i := 0; i < N; i++ {
		fmt.Scanf("%d %d", &a, &b)
		array[a] += b
	}

	cur := 0
	for i, v := range array {
		cur += v
		if cur >= K {
			fmt.Println(i)
			return
		}
	}
}


Measured memory_bytes: 7040
/*
ID: jerrywcy
LINK:
LANG: C++
STATUS:
*/
#include <bits/stdc++.h>

#define init(array,x) memset(array,x,sizeof(array))
#define pb push_back

using namespace std;

const int inf=0x3f3f3f3f;

int n,k;
double ans;

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for (int i=1;i<=n;i++){
		double tmp=1.0;
		int cur=i;
		while (cur<k){
			cur*=2;
			tmp/=2;
		}
		ans+=tmp/n;
	}
	printf("%.12lf\n",ans);

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

int main()
{
	int n;
	cin >> n;
	int taka,ao;
	cin >> taka >> ao;
	taka--;ao--;
	vector<vector<int>> mm(n);
	rep(i,n-1)
	{
		int foo,fooo;
		cin >> foo >> fooo;
		foo--;fooo--;
		mm[foo].push_back(fooo);
		mm[fooo].push_back(foo);
	}
	//cout<<"aaa"<<endl;
	vector<int> aocost(n,-1),takacost(n,-1);
	queue<int> Q;

	Q.push(ao);
	aocost[ao] = 0;
	
	while(!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		int nowcost = aocost[now];
		rep(i,mm[now].size())
		{
			if(aocost[mm[now][i]]==-1)
			{
				Q.push(mm[now][i]);
				aocost[mm[now][i]]=aocost[now]+1;
			}
		}
	}

	Q.push(taka);
	takacost[taka] = 0;
	int lastaocost=0;
	while(!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		int nowcost = takacost[now];
		lastaocost = max(lastaocost,aocost[now]);
		rep(i,mm[now].size())
		{
			if(takacost[mm[now][i]]==-1)
			{
				if(nowcost+1<aocost[mm[now][i]])
				{
					Q.push(mm[now][i]);
					takacost[mm[now][i]]=takacost[now]+1;
				}
			}
		}
	}
	//rep(i,n)cout<<takacost[i]<<endl;
	cout<<lastaocost-1<<endl;
	return 0;
}

Measured memory_bytes: 6656